# Condition number of $A^TA$

if $n \times n$ full rank matrix $A$ has condition number $\kappa$, what would be the condition number of $A^TA$? Preferably If the derivation includes the following definition of $\kappa$: $$\kappa = \sigma_{max} / \sigma_{min}$$ Where $\sigma$ are the non-zero singular-values of $A$.

I assume you mean the condition number defined by the Euclidean norm, i.e. $$\kappa = \|A\|\cdot \|A^{-1}\|$$ Note also that $\|A\| = \|\sqrt{A^TA}\|$. Conclude that $\kappa(A^TA) = \kappa(A)^2$.

• Not quite. You forgot a square. Also, this is assuming the operator norm induced by the Euclidean norm. There are other matrix norms that are used in defining condition numbers. Commented Jul 6, 2015 at 17:56
• Side note: one option for solving $Ax = b$ numerically could be to solve $A^T A x = A^T b$ using the conjugate gradient method, a method which requires the coefficient matrix to be symmetric. However, this approach has the disadvantage that the condition number of $A^T A$ is the square of the condition number of $A$. Commented Jul 6, 2015 at 18:05
• @RobertIsrael whoops, fixed. Thank you. Commented Jul 6, 2015 at 18:12
• $\|A\| \cdot \|A^{-1}\| = \lambda_{max}/\lambda_{min}$ when $A$ is symmetric, but this is not generally the case. The condition number is not usually defined to be the ratio of those eigenvalues. Can we assume that $A$ is symmetric? Commented Jul 7, 2015 at 18:31
• @Hayer in that case, then notice that $\|A\| = \sigma_{max}(A)$, and that $\|A^{-1}\| = \sigma_{max}(A^{-1}) = \frac 1{\sigma_{min}(A)}$ Commented Jul 8, 2015 at 3:31

The result is true for rectangular matrices.

Let $p\geq q$ and $A\in M_{p,q}(\mathbb{R})$ be a full column rank matrix. We consider $||A||_2=\sup \dfrac{||Ax||_2}{||x||_2}$ and $cond(A)=||A||.||A^+||$ where $A^+$ is the pseudo-inverse of $A$. Then $cond(A)^2=cond(A^TA)$ (exercise)

In particular, if we want to use the Gauss method of least squares for $Ax-b$, then we must solve $A^TAx=A^Tb$; thus the condition number of this calculation is $cond(A)^2$. Finally, if $A,b$ are known with $N$ significant digits and if $cond(A)\approx 10^k$, then $x$ is known with $N-2k$ significant digits.