Why is the condition number of a matrix given by these eigenvalues?

In the book, the condition number refers to the matrix $A \in \mathbb{R}^{n \times n}$, not the function as you stated in the question.

The condition number of a matrix $A$ is defined as

$$ \kappa(A) = \|A\|_2\|A^{-1}\|_2,$$

where $\| \cdot \|_2$ is spectral norm of a matrix. It is known that the spectral norm of a matrix equals its maximum singular value

$$ \|A\|_2 = \sigma_{max}(A) $$

and that the maximum singular value of $A^{-1}$ equals 1 over the minimum singular value of $A$

$$ \sigma_{max}(A^{-1}) = 1 / \sigma_{min}(A).$$

Thus,

$$ \kappa(A) = \sigma_{max}(A) / \sigma_{min}(A).$$

If the matrix $A$ is normal (which means $A$ can be decomposed as $A=Q \Lambda Q^T$ where $Q$ is an orthogonal matrix and $\Lambda$ is a diagonal matrix whose entries are the eigenvalues of $A$), and using the fact that $\sigma_i(A) = \sqrt{\lambda_i(A^TA)}$, we have

$$ \sigma_{max}(A) = \sqrt{\lambda_{max}(A^TA)} = \sqrt{\lambda_{max}((Q\Lambda Q^T)^TQ\Lambda Q^T)} = \sqrt{\lambda_{max}(Q\Lambda^2Q^T)} = \sqrt{\lambda_{max}(A)^2} = |\lambda_{max}(A)|, $$

and then we have

$$ \kappa(A) = |\lambda_{max}(A)|/|\lambda_{min}(A)|.$$

However, in the book, I do not see where the author mentions that the matrix $A$ is normal.


The book is wrong. The matrix must be normal. Existence of an eigenvalue decomposition is not enough (counter to what they claim on that page).

For example, the matrix $$\begin{bmatrix} 1 & 99 \\ 0 & 2 \end{bmatrix}$$ has a condition number of 4903 but eigenvalues $1$ and $2$. The condition number can be made arbitrarily bad by replacing 99 by 999, or 9999, and so on.

Conceptually, a matrix can be very badly conditioned if the eigenvectors point in nearly the same direction, even if the eigenvalues are similar.

To correct the issue, the author either needs to replace the eigenvalues by the singular values, or add additional conditions on the matrix.


$$\operatorname{cond}(A)=\dfrac{\max_{|w|=1}|Aw|}{\min_{|w|=1}|Aw|}$$using SVD we have$$A=UDV$$where $U$ and $V$ are unitary and $D$ is diagonal whose main diagonal entries are eigenvalues of $A$. Also |Uw|=|Vw|=|w| therefore$$\max_{|w|=1}|Aw|=\max_{|w|=1}|UDVw|=\max_{|w'|=1}|UDw'|=\max_{|w'|=1}|Dw'|=\max_{|w'|=1}\sqrt{|(\lambda_1w'_1)^2+(\lambda_2w'_2)^2+...+(\lambda_nw'_n)^2|}=|\lambda_{max}|$$also$$\min_{|w|=1}|Aw|=|\lambda_{min}|$$which completes our proof.