\magnification=\magstep1 \rightline{4-8-97 by HW} \medskip \centerline{{\bf On matrices for which norm bounds are attained.}} \bigskip \noindent Hans Schneider\footnote{$^*$}{Research supported by NSF Grant DMS-9424346} \smallskip {\sl \noindent Department of Mathematics \noindent Van Vleck Hall \noindent 480 Lincoln Drive \noindent University of Wisconsin-Madison \noindent Madison WI 53706 USA} \smallskip \noindent and \smallskip \noindent Hans F. Weinberger \smallskip {\sl \noindent School of Mathematics \noindent University of Minnesota \noindent 107 Vincent Hall \noindent 206 Church Street \noindent Minneapolis, MN, 55455 USA} \bigskip \centerline{April 1997} \vfil\eject ABSTRACT \medskip Let $\|A\|_{p,q}$ be the norm induced on the matrix $A$ with $n$ rows and $m$ columns by the H\"older $\ell_p$ and $\ell_q$ norms on $R^n$ and $R^m$ (or $C^n$ and $C^m$), respectively. It is easy to find an upper bound for the ratio $\|A\|_{r,s}/\|A\|_{p,q}$. In this paper we study the classes of matrices for which the upper bound is attained. We shall show that for fixed $A$, attainment of the bound wdepends only on the signs of $r-p$ and $s-q$. Various criteria depending on these signs are obtained. For the special case $p=q=2$, the set of all matrices for which the bound is attained is generated by means of singular value decompositions. \bigskip \hrule \bigskip %\vfil \eject \noindent 1. INTRODUCTION \bigskip Let $A$ be a matrix with $n$ rows and $m$ columns. If $A$ is considered as a complex transformation, let $\mu_1$ and $\mu_2$ be norms on $C^m$, and let $\nu_1$ and $\nu_2$ be norms on $C^n$. If $A$ is real and is considered as a transformation from $R^m$ to $R^n$, let the $\mu_i$ be norms on $R^m$ and the $\nu_i$ be norms on $R^n$. Define the induced norms $$ \|A\|^{(i)}=\max_{{\bf x}}\nu_i(A{\bf x})/\mu_i({\bf x}) $$ for $i=1$ and 2, where the maximum is taken over either $C^m$ or $R^m$, as is appropriate. It was shown in [SS] (see also [HJ, p.303]) that $$ \|A\|^{(2)}\le \max_{{\bf x}}{\mu_1({\bf x})\over\mu_2({\bf x})}\ \max_{{\bf y}}{\nu_2({\bf y})\over\nu_1({\bf y})}\ \|A\|^{(1)}, \leqno(1.1) $$ and that equality is always attained for some $A\ne 0$. Here the maxima are taken over $C^m$ and $C^n$ if $A$ is thought of as a complex transformation, and over $R^m$ and $R^n$ if $A$ is a real and its action is confined to $R^m$. In this work we shall be concerned with characterizing the set of all matrices $A$ for which equality is attained in (1.1), at least in some cases. We shall show that this set can be described by the following property. {\bf Theorem 1.} {\sl If equality holds in the inequality (1.1), then every maximizer ${\bf v}$ of the ratio $\nu_2(A{\bf x})/\mu_2({\bf x})$ has the properties that \item{(i)} {\bf v} is also a maximizer of the ratio $\mu_1({\bf x})/\mu_2({\bf x})$, \item{(ii)} $A{\bf v}$ is a maximizer of the ratio $\nu_2({\bf y})/\nu_1({\bf y})$, and \item{(iii)} ${\bf v}$ is also a maximizer of the ratio $\nu_1(A{\bf x})/\mu_1({\bf x})$. Conversely, if there is one maximizer $\bf v$ of $\nu_1(A{\bf x})/\mu_1({\bf x})$ which has the properties (i) and (ii), then equality holds in (1.1).} \smallskip Theorem 1 can only provide useful information if the two maxima on the right and the corresponding maximizers are known. Both of these conditions apply when the norms involved are H\"older norms. We denote the $\ell_p$ norm by $\|\ \|_p$. For any $p$ and $q$ in the interval $[1,\infty]$ we define the induced norm $$ \|A\|_{p,q}:=\max_{{\bf x}}{\|A{\bf x}\|_q\over\|{\bf x}\|_p}. \leqno(1.2) $$ The maximum of the ratio $\|{\bf x}\|_r/\|{\bf x}\|_p$ and the corresponding maximizers are well known. In order to state the result we recall that sgn$(z)$ is defined to be 1 if $z>0$, 0 if $z=0$, and -1 if $z<0$, and that $[z]_+$ is defined to be $z$ if $z\ge0$ and 0 if $z\le0$. We also define the three subsets of a real or complex vector space of $m$-tuples or $n$-tuples. $$ \eqalign{ &K_1=\{{\bf x}:\ {\rm all\ components\ of\ {\bf x}\ have\ equal\ absolute\ values}\}\cr &K_{-1}=\{{\bf x}:\ {\rm at\ most\ one\ component\ of\ {\bf x}\ differs\ from\ 0}\}\cr &K_0={\rm the\ whole\ vector\ space}.} \leqno(1.3) $$ The following result is found, e.g., in [HLP, p.~26 \#16 and p.~29\#19]. {\bf Proposition 1.} For any ${\bf x}$ in $R^m$ or $C^m$ $$ \|{\bf x}\|_r\le m^{[(1/r)-(1/p)]_+}\ \|{\bf x}\|_p\qquad {\rm for}\ p,r\in[1,\infty]. \leqno(1.4) $$ {\sl Equality holds if and only if the $m$-vector $\bf x$ lies in $K_{{\rm sgn}(p-r)}$.} \smallskip By inserting Proposition 1 into the inequality (1.1) and into Theorem 1, we immediately obtain the following special case for the H\"older spaces. {\bf Proposition 2.} $$ \|A\|_{r,s}\le m^{[(1/p)-(1/r)]_+}\ n^{[(1/s)-(1/q)]_+}\ \|A\|_{p,q} \qquad {\rm for}\ p,q,r,s \in [1,\infty]. \leqno(1.5) $$ {\sl If equality holds in this inequality, then every maximizer ${\bf v}$ of the ratio $\|A{\bf x}\|_s/\|{\bf x}\|_r$ has the properties \item{(i)} ${\bf v}\in K_{{-\rm sgn}(p-r)}$, \item{(ii)} $A{\bf v}\in K_{{\rm sgn}(q-s)}$, and \item{(iii)} ${\bf v}$ is a maximizer of the ratio $\|A{\bf x}\|_q/\|{\bf x}\|_p$. Conversely, if there exists a maximizer ${\bf v}$ of the ratio $\|A{\bf x}\|_q/\|{\bf x}\|_p$ which has the properties (i) and (ii), then equality holds in (1.5).} \smallskip \noindent For the case $m=n$, $q=p$, $s=r$, the inequality (1.5) was pointed out by Higham [H, p.124]. \smallskip \noindent {\bf Remark.} {\sl The inequality (1.5) is equivalent to the following monotonicity statement:} For fixed $s$, $\|A\|_{r,s}$ is nondecreasing and $m^{1/r}\|A\|_{r,s}$ is nonincreasing in $r$, and for fixed $r$, $n^{-1/s}\|A\|_{r,s}$ is nondecreasing and $\|A\|_{r,s}$ is nonincreasing in $s$. {\sl The inequality (1.5) obviously implies the above statement. It is not difficult to show that the converse is true. If, for instance, $p\le r$ and $q\le s$, then the monotonicity statement implies that $$ m^{1/r}\|A\|_{r,s}\le m^{1/p}\|A\|_{p,s}\le m^{1/p}\|A\|_{p,q}, $$ which implies the inequality (1.5) for this case.} \smallskip The trivial observation that for fixed $(p,q)$ the only dependence on $(r,s)$ in Proposition 2 is through the functions sgn$(p-r)$ and sgn$(q-s)$ immediately yields the following statement. {\bf Proposition 3.} {\sl If equality holds in (1.5) , if sgn$(p-r')$=sgn$(p-r)$, and if sgn$(q-s')$=sgn$(q-s)$, then equality also holds in (1.5) when the pair $(r,s)$ is replaced by $(r',s')$.} \smallskip {\bf Remark.} {\sl By using the inequality (1.5) with $r=p'$ and $s=q'$, one sees that Proposition 2 also shows that equality in (1.5) implies that %the same equality when $(p,q,r,s)$ is replaced by $$ \|A\|_{r',s'} = m^{[(1/p')-(1/r')]_+}\ n^{[(1/s')-(1/q')]_+}\ \|A\|_{p',q'}, \qquad {\rm for}\ p,q,r,s \in [1,\infty], %\leqno(1.5) $$ provided ${\rm sgn}(p'-r')={\rm sgn}(p-p')={\rm sgn}(p-r)$ and ${\rm sgn}(q'-s')={\rm sgn}(q-q')={\rm sgn}(q-s)$.} \smallskip Proposition 3 shows that for a prescribed pair $(p,q)$ with $1\le p,q\le\infty$, equality holds in (1.5) for some $r\ne p$ and $s\ne q$ if and only if $A$ lies in the appropriate one of at most four classes, which we shall label by the extremal pair $(r,s)$, that is, the pair in which each of these indices has the value 1 or $\infty$, for which equality holds in (1.5). That is, we define $$ \eqalign{ {\cal E}_{1,\infty}(p,q):=\{A:{\rm equality\ in\ (1.5)\ holds\ when}\ rq\}, \cr {\cal E}_{1,1}(p,q):=\{A:{\rm equality\ in\ (1.5)\ holds\ when}\ rp\ {\rm and}\ s>q\}, \cr {\cal E}_{\infty,1}(p,q):=\{A:{\rm equality\ in\ (1.5)\ holds\ when}\ r>p\ {\rm and}\ sq$, then %equality holds in (1.5) for $rq$ $A\in{\cal E}_{1,\infty}(p,q)$ if and only if $A$ has at most one nonzero entry.} \smallskip \noindent Theorem $3'$ in Section 3 shows that the Property (i) is sufficient for the existence of a $p>1$ and a $q<\infty$ such that $A\in {\cal E}_{1,\infty}(p,q)$. Section 4 deals with the cases in which $rp$ and $s>q$. We shall establish the following results. {\bf Theorem 4.} {\sl Let $\sigma$ denote the largest $\ell_1$ norm of the columns of $A$, so that $\sigma=\|A\|_{1,1}$. If $A\in{\cal E}_{1,1}(p,q)$ then $A$ has the properties \item{(i)} the entries of any column whose $\ell_1$ norm is equal to $\sigma$ all have the same absolute value $n^{-1}\sigma$, \item{(ii)} every column with this property is orthogonal to all the other columns of $A$, and \item{(iii)} $\sigma=n^{1-(1/q)}\|A\|_{p,q}$. Conversely, if the matrix $A$ has a column all of whose entries have the absolute values $n^{-1/q}\|A\|_{p,q}$, then $A\in{\cal E}_{1,1}(p,q)$. If $p>2$, then $A\in{\cal E}_{1,1}(p,q)$ if and only if $A$ has only one nonzero column, and all the entries of this column have the same absolute value.} \smallskip {\bf Theorem 5.} {\sl Let $\sigma$ denote the largest $\ell_1$ norm of the rows of $A$, so that $\sigma=\|A\|_{\infty,\infty}$. If $A\in{\cal E}_{\infty,\infty}(p,q)$, then $A$ has the properties \item{(i)} the entries of any row whose $\ell_1$ norm is equal to $\sigma$ all have the same absolute value $m^{-1}\sigma$, \item{(ii)} every row with this property is orthogonal to all the other rows of $A$, and \item{(iii)} $\sigma=m^{1/p}\|A\|_{p,q}$. Conversely, if the matrix $A$ has a row all of whose entries have the absolute values $m^{(1/p)-1}\|A\|_{p,q}$, then $A\in{\cal E}_{\infty,\infty}(p,q)$. If $q<2$, then $A\in{\cal E}_{\infty,\infty}(p,q)$ if and only if $A$ has only one nonzero row, and all the entries of this row have the same absolute value.} \smallskip Theorem $4'$ in Section 4 shows that the Properties (i) and (ii) of Theorem 4 are sufficient for the existence of $p>1$ and $q>1$ such that $A\in{\cal E}_{1,1}(p,q)$. Analogously, Theorem 5' states that the properties (i) and (ii) of Theorem 5 imply the existence of finite $p$ and $q$ such that $A\in{\cal E}_{\infty,\infty}(p,q)$ Section 5 considers the case where $r>p$ and $s2$, and $s<2$. Therefore the real norm $\|A\|_{r,s}$ is strictly less than $2^{(1/s)-(1/r)+(1/2)}$, and hence less than the complex norm, when $r>2$ and $s<2$. \bigskip \noindent 2. PROOFS OF THEOREMS 1 AND 2. \bigskip We begin by proving Theorem 1. {\sl Proof of Theorem 1.} We recall the derivation in [SS] of the inequality (1.1). For any $\bf x\ne 0$ with $A{\bf x}\ne 0$ we have $$ {\nu_2(A{\bf x})\over\mu_2({\bf x})}={\mu_1({\bf x})\over\mu_2({\bf x})}{\nu_2(A{\bf x})\over\nu_1(A{\bf x})}{\nu_1(A{\bf x})\over\mu_1({\bf x})}. \leqno(2.1) $$ Because the maximum of a product of nonnegative numbers is bounded by the product of the maxima, we obtain the inequality (1.1). Suppose there is a maximizer of the left-hand side of (2.1), which is not a maximizer of one of the factors on the right. Since all the factors are bounded by their maxima and one of them is strictly less than its maximum, the right-hand side of (1.1) is strictly greater than the left-hand side. Therefore the condition of Proposition 1 is necessary for equality. If there is a maximizer $\bf v$ of all three quotients on the right of (2.1), then the maximum of the left-hand side is bounded below by the right-hand side of (1.1). Since we already know that it is bounded above by the same quantity, we conclude that equality holds in (1.1). This establishes Theorem 1. \smallskip {\sl Proof of Theorem 2.} We observe that a maximizer of the ratio $\|A{\bf v}\|_2/\|{\bf v}\|_2$ is an eigenvector of the matrix $A^*A$ which corresponds to its largest eigenvalue. By Proposition 2, equality in (1.5) with $p=q=2$ implies that a maximizer $\bf v$ of $\|A{\bf x}\|_r/\|{\bf x}\|_q$ is such an eigenvector, that it is in $K_{-{\rm sgn}(2-r)}$, and that the eigenvector $A{\bf v}$ of $AA^*$ is in $K_{{\rm sgn}(2-s)}$. Thus we can construct (see. e.g., the proof of Theorem 2.3-1 in [GVL]) a singular value decomposition $A=U\Sigma V^*$ in which the first column of the unitary matrix $U$ is the vector $\|A{\bf v}\|_2^{-1}A{\bf v}\in K_{{\rm sgn}(2-s)}$ and the first row of the unitary matrix $V$ is $\|{\bf v}\|_2^{-1}{\bf v}\in K_{-{\rm sgn}(2-r)}$. The (11) element of the nonnegative diagonal matrix $\Sigma$ is the square root of the largest eigenvalue of $A^*A$, which is the maximal element of $\Sigma$. The converse follows from the fact that the first column of $V$ is a maximizer of $\|A{\bf x}\|_2/\|{\bf x}\|_2$ and the converse statement of Proposition 2, so that Theorem 2 is proved. {\bf Remark.} {\sl If the matrix $A$ is a scalar multiple of a unitary matrix and the absolute values of all its entries are equal to a number $\rho$, then $A$ has a singular value decomposition with $U=n^{-1/2}\rho^{-1}A$, $\Sigma=n^{1/2}\rho I$, and $V=I$, and another singular value decomposition with $U=I$, $\Sigma=n^{1/2}\rho I$, and $V=n^{-1/2}\rho^{-1}A^*$. Hence Theorem 2 shows that %equality holds %in (1.5) whenever $p=q=2$ and $r$ and $s$ are either both bounded above by %2 or bounded below by 2. $A$ lies in both ${\cal E}_{1,1}(2,2)$ and ${\cal E}_{\infty,\infty}(2,2)$. Examples of such matrices include the Hadamard matrices, which are orthogonal matrices whose entries have the values $\pm1$ (see [H, p.~128, \S6.13]), and the matrices which represent the finite Fourier transforms.} \bigskip %\vfil\eject \noindent 3. THE CLASS ${\cal E}_{1,\infty}(p,q)$. \bigskip The following lemma will be used in the proofs of Theorems 3, 4, and 6. We recall the definition of the conjugate index $p^*=p/(p-1)$ of an index $p$, and the fact that $A^*$ denotes the Hermitian transpose of the matrix $A$. We also recall the identity $$ \|A^*\|_{q^*,p^*}=\|A\|_{p,q}, \leqno(3.1) $$ which simply states that the norm of the adjoint of a transformation is equal to the norm of the transformation. {\bf Lemma 3.1.} {\sl Suppose that a maximizer $\bf v$ of $\|A{\bf x}\|_q/\|{\bf x}\|_p$ has the properties that \item{(i)} all its nonzero components have the same absolute value, and \item{(ii)} the same is true of $A{\bf v}$. \noindent If $11$, we can apply Lemma 3.2 to show that $\bf v$ is an eigenvector of $A^*A$. Therefore if $\bf x$ is a coordinate vector orthogonal to $\bf v$, it is also orthogonal to $A^*A{\bf v}$, which implies that $A{\bf x}$ is orthogonal to $A{\bf v}$. This means that a column which contains a single nonzero element of magnitude $\rho$ is orthogonal to all the other columns of $A$. In other words, an element of magnitude $\rho$ is also the only nonzero element of its row as well as of its column, so that Property (i) is established. If we choose a trial vector $\bf x$ whose components in the directions of the columns with elements of magnitude $\rho$ are zero, then $A{\bf x}=C{\bf x}$ where $C$ is defined in the statement of Theorem 1. Therefore $\|C\|_{p,q}\le\|A\|_{p,q}=\rho$. This is Property (ii). To prove the converse statement for $p\le q$, we define $B=A-C$, and decompose any vector $\bf x$ into ${\bf y}+{\bf z}$, where the components of $\bf z$ are zero in the directions corresponding to columns which contain elements of magnitude $\rho$ and the components of $\bf y$ in the remaining directions vanish. Then by Property (i) and two applications of Proposition 1 $$ \eqalign{ \|A{\bf x}\|_q&=\{(\rho\|{\bf y}\|_q)^q+\|C{\bf z}\|_q^q\}^{1/q}\cr &\le\{(\rho\|{\bf y}\|_p)^q+(\|C\|_{p,q}\|{\bf z}\|_p)^q\}^{1/q}\cr &\le\{(\rho\|{\bf y}\|_p)^p+(\|C\|_{p,q}\|{\bf z}\|_p)^p\}^{1/p}\cr &\le\max\{\rho,\|C\|_{p,q}\}\|{\bf x}\|_p.} $$ That is, $$ \|A\|_{p,q}=\max\{\rho,\|C\|_{p,q}\}. \leqno(3.2) $$ Thus Property (ii) shows that $\|A\|_{p,q}=\rho=\|A\|_{1,\infty}$, and the proof of the converse statement is complete. To prove the last assertion of Theorem 3 assume that $p>q$ and that $A\in{\cal E}_{1,\infty}(p,q)$. Choose a trial vector $\bf x$ whose component in the direction of a column with a singleton element of magnitude $\rho$ is one and which has one other nonzero component $\alpha$. Let $b$ be any entry of $A$ in the column which corresponds to $\alpha$. Then because $p>q$, $$ {\|A{\bf x}\|_q\over\|{\bf x}\|_p} \ge {(\rho^q+|\alpha b|^q)^{1/q}\over(1+|\alpha|^p)^{1/p}} =\rho+(1/p)\rho^{1-q}|b|^q|\alpha|^q+o(|\alpha|^q) $$ for small $\alpha$. Because $\rho=\|A\|_{p,q}$, the right-hand side must be bounded by $\rho$, and we conclude that $b=0$. Because $b$ is an arbitrary element of any column other than that with the entry of magnitude $\rho$, we conclude that all other columns of $A$ are zero, so that $A$ has only one nonzero entry. Finally, a simple computation shows that if $A$ has only one nonzero entry, and if the magnitude of this entry is $\rho$, then $\|A\|_{r,s}=\rho$ for all $r$ and $s$, so that $A\in{\cal E}_{1,\infty}(p,q)$. Thus all parts of Theorem 3 have been established. \smallskip Because it is difficult to compute the $p,q$ norm for most $p$ and $q$, it is difficult to verify Property (ii) of Theorem 3. We shall show that the easily verified Property (i) is sufficient to assure the existence of some $p>1$ and $s<\infty$ such that equality holds in (1.5) when $rq$. {\bf Theorem $3'$.} {\sl Let $A$ have Property (i) of Theorem 3. Let $C$ be the matrix obtained from $A$ by replacing all elements of absolute value $\rho=\|A\|_{1,\infty}$ by 0, so that $\|C\|_{1,\infty}<\rho$. If $p$ and $q$ satisfy the inequalities $p\le q$ and $$ m^{1-(1/p)}n^{(1/q)}\|C\|_{1,\infty}\le \rho, \leqno(3.3) $$ then $A\in{\cal E}_{1,\infty}(p,q)$. The inequality (3.3) is satisfied if $p$ is sufficiently close to $1$ and $q$ is sufficiently large.} \smallskip {\sl Proof.} Since (1.5) shows that $$ \|C\|_{p,q}\le m^{1-(1/p)}n^{1/p}\|C\|_{1,\infty}, $$ the inequality (3.3) and the equation (3.2) imply that $\|A\|_{p,q}=\rho$. That is, Property (ii) of Theorem 3 holds, and the conclusion $A\in{\cal E}_{1,\infty}(p,q)$ follows. \bigskip \noindent 4. THE CLASSES ${\cal E}_{1,1}(p,q)$ AND ${\cal E}_{\infty,\infty}(p,q)$. \bigskip {\sl Proof of Theorem 4.} Suppose that $A\in{\cal E}_{1,1}(p,q)$, so that equality holds in (1.5) with $r=s=1$. The triangle inequality shows that $\|A{\bf x}\|_1/\|{\bf x}\|_1\le \sigma$, the largest $\ell_1$ norm of the columns of $A$. Moreover, this bound is attained when $\bf x$ is in the direction of any coordinate whose corresponding column has the $\ell_1$ norm $\sigma$. Thus if $\bf v$ is a coordinate vector in such a direction, it is a maximizer for the ratio. Proposition 2 states that if $\bf v$ is a unit vector in one of these coordinate directions, the elements of the corresponding column $A{\bf v}$ must have equal absolute values, and $\bf v$ must also be a maximizer of $\|A{\bf x}\|_q/\|{\bf x}\|_p$. These two facts give the properties (i) and (iii) of Theorem 3. Since $p>1$, Lemma 3.1 shows that $\bf v$ is an eigenvector of $A^*A$. As in the proof of Theorem 3, this implies that if $\bf x$ is a coordinate vector perpendicular to $\bf v$, then it is also perpendicular to $A^*A{\bf v}$, so that the column $A{\bf x}$ is perpendicular to $A{\bf v}$. This is the property (ii) To prove the converse statement, we observe that if $A$ has a column whose elements have the absolute value $n^{-1/q}\|A\|_{p,q}$, then a unit vector $\bf v$ in the direction of this column is a maximizer of the ratio $\|A{\bf x}\|_q/\|{\bf x}\|_p$. Therefore the converse statement of Proposition 2 implies that equality holds in (1.5), and hence that $A\in{\cal E}_{1,1}(p,q)$. To prove the last statement of Theorem 4, we suppose that $A\in{\cal E}_{1,1}(p,q)$, and that $p>2$. Then there is at least one column $\bf c$ of $A$ all of whose entries have the absolute value $n^{-1}\sigma=n^{-1/q}\|A\|_{p,q}$. Let $\bf c$ be one such column, let $\bf b$ be any other column of $A$, and let $\alpha$ be a real parameter. The adjoint relation (3.1) leads to the inequality $$ \|A^*({\bf c}+\alpha{\bf b})\|_{p^*}\le\|A\|_{p,q}\|{\bf c}+\alpha{\bf b}\|_{q^*}=n^{-1+(1/q)}\sigma\|{\bf c}+\alpha{\bf b}\|_{q^*}. \leqno(4.1) $$ We observe that for small $\alpha$ $$ |c_j+\alpha b_j|^{q^*}=|c_j|^{q^*}+q^*\ {\rm Re}(\alpha|c_j|^{q^*-2}\bar{c_j}b_j)+O(\alpha^2). $$ We sum on $j$ and use the properties that the entries of $\bf c$ all have the absolute value $n^{-1}\sigma$ and that $\bf b$ is orthogonal to $\bf c$ to find that $$ \|{\bf c}+\alpha{\bf b}\|_{q^*}^{q^*}=n^{-1+(1/q^*)}\sigma+O(\alpha^2)=n^{-1/q}\sigma+O(\alpha^2). \leqno(4.2) $$ Since $\bf c$ and $\bf b$ are orthogonal, the entry of $A^*({\bf c}+\alpha{\bf b})$ which corresponds to the column $\bf c$ is $n^{-1}\sigma^2$, while the entry which corresponds to the column $\bf b$ is $\alpha\|{\bf b}\|_2^2$. We obtain a lower bound for the left-hand side of (4.1) by replacing all the other entries by zero. For small $\alpha$ this lower bound takes the form $$ \|A^*({\bf c}+\alpha{\bf b})\|_{p^*} \ge n^{-1}\sigma^2+(p^*)^{-1}(n^{-1}\sigma^2)^{1-p^*}\|{\bf b}\|_2^{2p^*}\alpha^{p^*} +O(\alpha^{2p^*}). $$ where $K>0$. By putting this and (4.2) into (4.1), we find the inequality $$ n^{-1}\sigma^2+(p^*)^{-1}(n^{-1}\sigma^2)^{1-p^*}\|{\bf b}\|_2^{2p^*}\alpha^{p^*} +O(\alpha^{2p^*})\le n^{-1}\sigma^2+O(\alpha^2). $$ We observe that $p^*<2$ because $p>2$. We cancel the first terms from the two sides, divide by $\alpha^{p^*}$, and let $\alpha$ approach zero to see that $\|{\bf b}\|_2=0$. That is, every column other than $\bf c$ is zero. This establishes the last statement of Theorem 4, and the Theorem is proved. \smallskip Theorem 5 will follow easily from Theorem 4 and the following lemma. {\bf Lemma 4.1.} {\sl If equality holds in (1.5), then equality also holds when $A$ is replaced by $A^*$, the pair $(r,s)$ is replaced by $(s^*,r^*)$, and the pair $(p,q)$ is replaced by $(q^*,p^*)$.} {\sl Proof.} We recall the adjoint equation (3.1), namely $\|A^*\|_{q^*,p^*}=\|A\|_{p,q}$ We also note that in going from $A$ to $A^*$ the dimensions $m$ and $n$ are interchanged, and that by definition $(1/q^*)-(1/s^*)=(1/s)-(1/q)$ and $(1/r^*)-(1/p^*)=(1/p)-(1/r)$. Therefore, the replacements indicated in the Lemma leave both sides of (1.5) unchanged, which proves the Lemma. \smallskip {\sl Proof of Theorem 5.} By Lemma 4.1, $A\in{\cal E}_{\infty,\infty}(p,q)$ if and only if $A^*\in{\cal E}_{1,1}(q^*,p^*)$. Since $s>q$ implies $s^*p$ implies $r^* p$ and $s