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|}< \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}} < \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.