6
$\begingroup$

${\bf A}$ is $n \times n$ matrix. I want to know why the condition number of ${\bf A}$ is given by:

$$\frac{\rm{max}(\lambda_i)}{\rm{min}(\lambda_j)},$$

where $\lambda$ are eigenvalues of ${\bf A}$. Would you please give me a proof?

This equation come from the page 80 in "Deep Learning" written by Ian Goodfellow.

$\endgroup$
3
  • $\begingroup$ What is the condition number ? $\endgroup$
    – Suzet
    Commented Jun 12, 2018 at 23:39
  • 2
    $\begingroup$ read this document en.wikipedia.org/wiki/Condition_number $\endgroup$
    – Sakurai.JJ
    Commented Jun 12, 2018 at 23:44
  • 5
    $\begingroup$ The book is wrong. They either need replace the eigenvalues with singular values, or add additional conditions onto the matrix. $\endgroup$
    – Nick Alger
    Commented Jun 15, 2018 at 3:28

3 Answers 3

14
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ @Sakurai.JJ The condition number concept in the first equation here can be discovered by trying to bound the amount that the solution to $Ax=b$ changes when $b$ changes by a small amount. Hopefully, the solution will not change much. Otherwise, small errors in our estimate of $b$ might lead to disastrous errors in our estimate of $x$. The condition number measures how "close to singular" a matrix is. This is discussed for example in Strang's book Linear Algebra and Its Applications (and a lot of other books). $\endgroup$
    – littleO
    Commented Jun 15, 2018 at 0:49
  • 1
    $\begingroup$ “However, in the book, I do not see where the author mentions that the matrix A is normal.” — Directly above equation (4.2) it says: “When $A \in \mathbb R^{n\times n}$ has an eigenvalue decomposition”, which I'd read as “is diagonalizable”. Which is exactly the condition you give for normality. $\endgroup$
    – celtschk
    Commented Jun 15, 2018 at 5:19
  • 2
    $\begingroup$ @celtschk Normality and the existence of an eigenvalue decomposition are not equivalent. See my post below for a counterexample. $\endgroup$
    – Nick Alger
    Commented Jun 15, 2018 at 5:22
  • 2
    $\begingroup$ @NickAlger: Actually the book doesn't say $|\lambda_{\max}/\lambda_{\min}|$, but $\max_{i,j}|\lambda_i/\lambda_j|$, see eq. (4.2). But when you say $|\lambda_{\max}/\lambda_{\min}|$ what is meant with $\lambda_{\max/\min}$ in this context is the eigenvalue with maximal/minimal absolute value (note that this is also used for complex matrices, where comparing the eigenvalues themselves would not even make sense). $\endgroup$
    – celtschk
    Commented Jun 15, 2018 at 5:30
  • 1
    $\begingroup$ @celtschk Thanks for pointing that out. However, that does not have any bearing on the example matrix $\begin{bmatrix}1 & 99 \\ 0 & 2\end{bmatrix}$, which has eigenvalues $1$ and $2$ but condition number approximately 5000. $\endgroup$
    – Nick Alger
    Commented Jun 15, 2018 at 5:34
8
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Well, he's talking about the condition number of the matrix. You're (maybe) talking about the condition number of an equation. The same claim is in Numerical Linear Algebra by Trefethen and Bau. see 12.16 on page 94. The condition number you are referencing is of, e.g., the problem Ax=b, see their theorem 12.1, same page. $\endgroup$
    – pdb
    Commented Nov 12, 2021 at 22:06
  • 1
    $\begingroup$ @pdb The $\sigma$ used in the definition of the condition number on page 94 of Trefethen and Bau is the singular value. Look up the page, it is clearly stated. Or just look in any other linear algebra book. In contrast, the deep learning book states they are using the eigenvalue, which is not correct because singular values do not always equal eigenvalues. But take a step back and think about it. Should the matrix $\begin{bmatrix} 1 & 999999999 \\ 0 & 2\end{bmatrix}$ should be considered "well conditioned"? It's eigenvalues are 1 and 2, but it is a horrible matrix for numerical calculations. $\endgroup$
    – Nick Alger
    Commented Nov 12, 2021 at 23:46
  • $\begingroup$ If you are skeptical that the official definition uses singular values, simply type cond([1,99; 0, 2]) into matlab, or np.linalg.cond([[1,99],[0,2]]) into numpy/python, or similar in any matrix library in any programming language. $\endgroup$
    – Nick Alger
    Commented Nov 13, 2021 at 0:00
  • $\begingroup$ Agreed, I had misread T&B. Thanks for explaining it. $\endgroup$
    – pdb
    Commented Nov 14, 2021 at 1:40
5
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Thank you. Is first equation the definition of condition number? And the determinant of unitary matrix is $\pm1$. So I think $|Uw| = |U||w| =\pm|w|$, right? $\endgroup$
    – Sakurai.JJ
    Commented Jun 12, 2018 at 23:54
  • 1
    $\begingroup$ You're welcome........the norm of such a vector is usually a 2-norm or $|Uv|=\sqrt{(Uv)^HUv}=\sqrt{v^HU^HUv}=\sqrt{v^Hv}=|v|$ $\endgroup$ Commented Jun 14, 2018 at 9:56
  • $\begingroup$ Oh, I understand. $\endgroup$
    – Sakurai.JJ
    Commented Jun 15, 2018 at 0:25
  • 2
    $\begingroup$ Here the diagonal entries of $D$ are the singular values, not the eigenvalues. $\endgroup$
    – Nick Alger
    Commented Jun 15, 2018 at 5:19
  • $\begingroup$ I see. Thank you. $\endgroup$
    – Sakurai.JJ
    Commented Jun 15, 2018 at 7:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .