Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
    
Let $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? –  littleO Oct 30 '12 at 8:02
add comment

1 Answer

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.