TAOCP 1.2.3 Exercise 35
Let M = \sup_{R(j)} a_j .
Section 1.2.3: Sums and Products
Exercise 35. [HM20] The notation $\sup_{R(j)} a_j$ is used to denote the least upper bound of the elements $a_j$, in a manner exactly analogous to the $\sum$- and $\prod$-notations. (When $R(j)$ is satisfied for only finitely many $j$, the notation $\max_{R(j)} a_j$ is often used to denote the same quantity.) Show how rules (a), (b), (c), and (d) can be adapted for manipulation of this notation. In particular discuss the following analog of rule (a):
$$(\sup\nolimits_{R(i)} a_i) + (\sup\nolimits_{S(j)} b_j) = \sup\nolimits_{R(i)} (\sup\nolimits_{S(j)} (a_i + b_j)),$$
and give a suitable definition for the notation when $R(j)$ is satisfied for no $j$.
Exercises
Determinants and matrices. The following interesting problems are for the reader who has experienced at least an introduction to determinants and elementary matrix theory. A determinant may be evaluated by astutely combining the operations of: (a) factoring a quantity out of a row or column; (b) adding a multiple of one row (or column) to another row (or column); (c) expanding by cofactors. The simplest and most often used version of operation (c) is to simply delete the entire first row and column, provided that the element in the upper left corner is $+1$ and the remaining elements in either the entire first row or the entire first column are zero; then evaluate the resulting smaller determinant. In general, the cofactor of an element $a_{ij}$ in an $n \times n$ determinant is $(-1)^{i+j}$ times the $(n-1) \times (n-1)$ determinant obtained by deleting the row and column in which $a_{ij}$ appeared. The value of a determinant is equal to $\sum a_{ij} \cdot \text{cofactor}(a_{ij})$ summed with either $i$ or $j$ held constant and with the other subscript varying from 1 to $n$.
If $(b_{ij})$ is the inverse of matrix $(a_{ij})$, then $b_{ij}$ equals the cofactor of $a_{ji}$ (not $a_{ij}$), divided by the determinant of the whole matrix.
The following types of matrices are of special importance:
Vandermonde’s matrix,
$a_{ij} = x_j^i$ $$ \begin{pmatrix} x_1 & x_2 & \ldots & x_n \ x_1^2 & x_2^2 & \ldots & x_n^2 \ \vdots & & & \vdots \ x_1^n & x_2^n & \ldots & x_n^n \end{pmatrix} $$
Combinatorial matrix, $a_{ij} = y + \delta_{ij}x$ $$ \begin{pmatrix} x+y & y & \ldots & y \ y & x+y & \ldots & y \ \vdots & & & \vdots \ y & y & \ldots & x+y \end{pmatrix} $$
Cauchy’s matrix, $a_{ij} = 1/(x_i + y_j)$ $$ \begin{pmatrix} 1/(x_1 + y_1) & 1/(x_1 + y_2) & \ldots & 1/(x_1 + y_n) \ 1/(x_2 + y_1) & 1/(x_2 + y_2) & \ldots & 1/(x_2 + y_n) \ \vdots & & & \vdots \ 1/(x_n + y_1) & 1/(x_n + y_2) & \ldots & 1/(x_n + y_n) \end{pmatrix} $$
Verified: yes
Solve time: 45s
Solution
Let
$$ M = \sup_{R(j)} a_j . $$
By definition, $M$ is characterized by the two conditions
$$ a_j \le M \qquad \text{for all } j \text{ satisfying } R(j), $$
and
$$ L < M \implies \text{there exists } j \text{ satisfying } R(j) \text{ such that } L < a_j . $$
The rules corresponding to (a), (b), (c), and (d) are as follows.
For rule (a), the direct analog of (4) is
$$ (\sup\nolimits_{R(i)} a_i) + (\sup\nolimits_{S(j)} b_j) = \sup\nolimits_{R(i)} \sup\nolimits_{S(j)} (a_i+b_j). \eqno(1) $$
Let
$$ A=\sup_{R(i)} a_i,\qquad B=\sup_{S(j)} b_j. $$
Then
$$ a_i\le A,\qquad b_j\le B, $$
for all admissible $i$ and $j$. Hence
$$ a_i+b_j\le A+B, $$
so $A+B$ is an upper bound for all values $a_i+b_j$. Therefore
$$ \sup_{R(i)}\sup_{S(j)}(a_i+b_j)\le A+B. $$
To prove the reverse inequality, let $\epsilon>0$. Since $A$ is the least upper bound, there exists $i$ satisfying $R(i)$ such that
$$ A-\frac{\epsilon}{2}<a_i. $$
Similarly, there exists $j$ satisfying $S(j)$ such that
$$ B-\frac{\epsilon}{2}<b_j. $$
Adding,
$$ A+B-\epsilon<a_i+b_j. $$
Hence
$$ A+B-\epsilon < \sup_{R(i)}\sup_{S(j)}(a_i+b_j). $$
Since this holds for every $\epsilon>0$,
$$ A+B \le \sup_{R(i)}\sup_{S(j)}(a_i+b_j). $$
Combining the two inequalities proves (1).
The corresponding multiplicative formula is generally false:
$$ (\sup\nolimits_{R(i)} a_i)(\sup\nolimits_{S(j)} b_j) = \sup\nolimits_{R(i)}\sup\nolimits_{S(j)}(a_ib_j) $$
need not hold when negative values occur. For example, if
$$ a_1=-1,\qquad b_1=-1, $$
then the left-hand side equals $1$, while the right-hand side equals
$$ \sup(-1\cdot -1)=1. $$
But if
$$ a_1=-2,\qquad a_2=1,\qquad b_1=-2,\qquad b_2=1, $$
then
$$ (\sup a_i)(\sup b_j)=1, $$
while
$$ \sup(a_ib_j)=4. $$
Thus addition is the natural operation associated with $\sup$.
Rule (b) becomes
$$ \sup_{R(i)} a_i = \sup_{R(j)} a_j = \sup_{R(p(j))} a_{p(j)}, \eqno(2) $$
provided that $p$ is a permutation of the relevant values, exactly as in (5). The proof is immediate, since the sets of values being considered are identical.
Rule (c) becomes
$$ \sup_{R(i)} \sup_{S(j)} a_{ij} = \sup_{S(j)} \sup_{R(i)} a_{ij}. \eqno(3) $$
Both sides equal the least upper bound of the set of all $a_{ij}$ for which both $R(i)$ and $S(j)$ hold.
More generally, corresponding to (9),
$$ \sup_{R(i)} \sup_{S(i,j)} a_{ij} = \sup_{S'(j)} \sup_{R'(i,j)} a_{ij}, \eqno(4) $$
where $S'(j)$ and $R'(i,j)$ are defined exactly as in the discussion following (9). Again, both sides represent the least upper bound of the same set of values.
Rule (d) becomes
$$ \sup_{R(j)\text{ or }S(j)} a_j = \max!\left( \sup_{R(j)} a_j,, \sup_{S(j)} a_j \right). \eqno(5) $$
Indeed, the set of all $a_j$ satisfying $R(j)$ or $S(j)$ is the union of the two corresponding sets, and the least upper bound of a union is the maximum of the two least upper bounds.
Finally, when no integer $j$ satisfies $R(j)$, the notation
$$ \sup_{R(j)} a_j $$
should be defined to be $-\infty$. With this convention, formulas such as
$$ \sup_{R(j)\text{ or }S(j)} a_j = \max!\left( \sup_{R(j)} a_j,, \sup_{S(j)} a_j \right) $$
remain valid even when one of the domains is empty. This convention is analogous to defining an empty product to be $1$. ∎