If A is $m \times n$ matrix such that $ m \geq n $ and B is a block matrix of form $ \begin{bmatrix}I & A \\ A^T & 0 \end{bmatrix} $, then what is the condition number of B in terms of singular values of A ?
Linear Algebra Question (SVD and Condition Number)
-
0Let $A = U \Sigma V^T$ be an SVD of $A$. Then B = \begin{bmatrix} U & \\ & V \end{bmatrix} \begin{bmatrix} I & \Sigma \\ \Sigma & 0 \end{bmatrix} \begin{bmatrix} U^T & \\ &V^T \end{bmatrix}. We only need to find the condition number of matrix \begin{bmatrix} I & \Sigma \\ \Sigma & 0 \end{bmatrix}, which has diagonal blocks. Does anyone know an easy way to do this? – 2012-10-30
1 Answers
I assume you're using the condition number with respect to the Euclidean norm.
Presumably $A$ has real entries. Then $B$ is symmetric. $\pmatrix{u\cr v\cr}$ is an eigenvector of $B$ for eigenvalue $\lambda$ iff $A^T u = \lambda v$ and $u + A v = \lambda u$. Then $A A^T u = \lambda A v = \lambda (\lambda - 1) u$ and $A^T A v = A^T (\lambda - 1) u = \lambda (\lambda - 1) v$. Conversely, if $A A^T$ has an eigenvector $u$ for eigenvalue $ \lambda (\lambda - 1)$ with $\lambda \ne 0$ and we take $v = \lambda^{-1} A^T u$, we get $u + A v = u + \lambda^{-1} A A^T u = \lambda u$, so $\pmatrix{u\cr v\cr}$ is an eigenvector of $B$ for eigenvalue $\lambda$. If $A^T A$ has an eigenvector $v$ for eigenvalue $\lambda (\lambda - 1)$ with $\lambda \ne 1$ and we take $u = (\lambda - 1)^{-1} A v$, then $A^T u = (\lambda - 1)^{-1} A^T A v = \lambda v$, and again $\pmatrix{u\cr v\cr}$ is an eigenvector of $B$ for eigenvalue $\lambda$.
By convention, one often omits the $0$ eigenvalues from the singular values of $A$, but we see that if $A$ has fewer than $n$ nonzero singular values (counted by multiplicity), $0$ is an eigenvalue of $A^T A$, implying that $0$ is an eigenvalue of $B$, and then the condition number of $B$ is $\infty$.
If $0$ is an eigenvalue of $A A^T$, which is always the case if $m > n$, then $1$ is an eigenvalue of $B$.
Other than that, if $\sigma_1 \le \sigma_2 \le \ldots \le \sigma_n$ are the singular values of $A$, $\sigma_1^2 \le \sigma_2^2 \le \ldots \le \sigma_n^2$ are the eigenvalues of $A^T A$ and the nonzero eigenvalues of $A A^T$, and so the eigenvalues of $B$ (other than $1$) are the solutions of $\lambda (\lambda - 1) = \sigma_j^2$, i.e. $\dfrac{1 \pm \sqrt{1+4\sigma^2}}{2}$. The largest of these in absolute value is $(1 + \sqrt{1+4 \sigma_n^2})/2$, so this is $\|B\|$. The least in absolute value is $(1 - \sqrt{1+4\sigma_1^2})/2$ (or $1$ if that is less and $0$ is an eigenvalue of $A A^T$), and the reciprocal of that is the greatest in absolute value of the eigenvalues of $B^{-1}$. Thus $\|B^{-1}\|$ is either $2/(\sqrt{1+4\sigma_1^2}-1)$ or $1$. We conclude that the condition number of $\|B\| \|B^{-1}\|$ of $B$ is either $\dfrac{1+\sqrt{1+4\sigma_n^2}}{2}$ or $\dfrac{1 + \sqrt{1+4\sigma_n^2}}{\sqrt{1+4\sigma_1^2}-1}$.