Norm of a Matrix Homework: Show ||A|| $\leq$ $\lambda \sqrt{mn}$

[Yagoda]

Homework Statement

Let \textbf{A} be an m x n matrix and \lambda = \max\{ |a_{ij}| : 1 \leq i \leq m, 1 \leq j \leq n \}.

Show that the norm of the matrix ||\textbf{A}|| \leq \lambda \sqrt{mn}.

Homework Equations

The definition I have of the norm is that ||\textbf{A}|| is the smallest number such that |\textbf{Ax}| \leq ||\textbf{A}|| \, |\textbf{x}| for all \textbf{x} in ℝⁿ.

The Attempt at a Solution

I let \textbf{y} = \textbf{Ax} and so |\textbf{y}| = \sqrt{\sum_{i=1}^{m}y_i^2}.
I started by looking at a matrix \textbf{A} with all the same entries so that any entry could be thought of as \lambda. So when you calculate |\textbf{y}| you will get m \lambda^2's under the radical along with sum of the x_1, \dots, x_n squared. So in the more general case that not all the entires of \textbf{A} are equal I can see how \lambda would provide an upper bound.
But I'm having trouble seeing how the \sqrt{n} comes into it.

 

[brmath]

So let A = $\begin{pmatrix} a& a & a \\ a & a & a\\ \end{pmatrix}$

(It's easier to type a than $\lambda$)

and multiply it by X = (x,y,z). You get AX = $\begin{pmatrix} ax +& ay + & az \\ ax+ & ay + & az\\ \end{pmatrix}$

You started correctly computing the ||AX|| and got to where |AX| = a$\sqrt 2 \sqrt{x^2 + y^2 + z^2}$.

To see where the n comes in take X = (1,1,1,). Now what is ||AX|| less than?

In finishing up, keep in mind that the < must work for every possible X. So it is perfectly possible there is an X which forces ||A|| lower. This is a bound, but for a given A it may not be the least upper bound.

 

[Yagoda]

If X = (1,1,1) then |\textbf{Ax}| = a \sqrt{2}\sqrt{3}, but I guess I am missing what happens if X is a different vector, say (1,2,3). Then |\textbf{Ax}| = a \sqrt{2}\sqrt{14}, which isn't less than a \sqrt{2}\sqrt{3}. I think in this case \textbf{||A||}= \frac{a\sqrt{72}}{\sqrt{14}} so in this case \textbf{||A||} \, \textbf{|x|}&lt; \lambda \sqrt{mn}. But my trouble is generalizing it.

 

[Yagoda]

After fiddling a little bit with the inequalities, it seems like in the general case it would be helpful to show that \frac{x_1 + x_2 + \dots + x_n}{\sqrt{x_1^2 + \dots + x_n^2}} &lt; \sqrt{n}.
Would this be a proper approach? And if so, is there some glaringly obvious fact I'm missing that would help me show this?

 

[brmath]

Let X = $(x_1,x_2,x_3)$. Let |x| be the largest of the 3 components. From our previous work we have ||AX|| $\le a \sqrt 2 \sqrt {x_1^2+x_2^2 + x_3^2} \le a \sqrt 2 \sqrt 3 |x|$.

Go back to your definition of ||AX||. This is the smallest number C such that $||Ax|| \le C ||x||$ for every vector X. We have shown (generalizing from the 3x2 case) that there is one vector x = (1,1,1...) such that ||Ax|| $\le a \sqrt m \sqrt n |x| \le a \sqrt m \sqrt n||X||$. So there is no way that C can be greater than $a \sqrt m \sqrt n$. It could be smaller than that, which is why we have the inequality.

All this computation depended on A consisting of all a's. To finish up, you need to redo this deduction when A has varying entries $a_{ij}$. In this case, choose $a = max|a_{ij}|$ and proceed more or less as we did before.