Is the Condition Number of A'A Related to its Matrix Norm?

[mathmari]

Hey!

We have a matrix $A\in \mathbb{R}^{m\times n}$ which has the rank $n$. The condition number is defined as $\displaystyle{k(A)=\frac{\max_{\|x\|=1}\|Ax\|}{\min_{\|x\|=1}\|Ax\|}}$.

I want to show that $k_2(A^TA)=\left (k_2(A)\right )^2$. We have that $$k_2(A^TA)=\frac{\max_{\|x\|_2=1}\|(A^TA)x\|_2}{\min_{\|x\|_2=1}\|(A^TA)x\|_2}$$

It holds that $$\|(A^TA)x\|_2=\left ((A^TA)x, (A^TA)x\right )=\left (A^TAx\right )^T\left (A^TAx\right )=x^TA^TAA^TAx=\left (Ax\right )^T\left (AA^T\right )\left (Ax\right )$$
We also have that $$\|Ax\|_2=\left (Ax, Ax\right )=\left (Ax\right )^T\left (Ax\right )=x^TA^TAx=x^T\left (A^TA\right )x$$

How do we continue? (Wondering)

 

[I like Serena]

Hey mathmari!

Shouldn't it be $\|Ax\|_2 = \sqrt{(Ax,Ax)}$ or $\|Ax\|_2^2 = (Ax,Ax)$? (Worried)

So we have:
$$\|Ax\|_2^2=x^T\left (A^TA\right )x$$

We also have:
$$\|(A^TA)x\|_2^2=x^TA^TAA^TAx=x^T(A^TA)^2x$$

Suppose $x$ is a vector of unit length for which $x^T\left (A^TA\right )x$ takes on its maximal value.
Then $x^T(A^TA)^2x$ will also take its maximal value, won't it? (Wondering)

 

[mathmari]

Shouldn't it be $\|Ax\|_2 = \sqrt{(Ax,Ax)}$ or $\|Ax\|_2^2 = (Ax,Ax)$? (Worried)

Ohh yes! (Blush)

So we have:
$$\|Ax\|_2^2=x^T\left (A^TA\right )x$$

We also have:
$$\|(A^TA)x\|_2^2=x^TA^TAA^TAx=x^T(A^TA)^2x$$

Suppose $x$ is a vector of unit length for which $x^T\left (A^TA\right )x$ takes on its maximal value.
Then $x^T(A^TA)^2x$ will also take its maximal value, won't it? (Wondering)

Will $x^T(A^TA)^2x$ take also its maximal value because the term in the middle is the square of the previous one? (Wondering)

 

[I like Serena]

Will $x^T(A^TA)^2x$ take also its maximal value because the term in the middle is the square of the previous one?

Well, to be fair, this is not immediately obvious. (Worried)

Let's take a slightly different angle.

According to the wiki page about matrix norms, a matrix $A$ has norm $\|A\|_2 =\sup\limits_{\|x\|=1} \|Ax\|_2 = \sqrt{\lambda_{\text{max}}(A^*A)}=\sigma_{\text{max}}(A)$, where $A^*$ is the conjugate transpose, which is just the transpose $A^T$ for a real matrix.

So $\|A^TA\|_2 = \sqrt{\lambda_{\text{max}}((A^TA)^T A^TA)}$, isn't it? (Wondering)