1
$\begingroup$

I saw this post on the eigenvalues of a matrix plus a constant times the identity matrix.

Say $A$ is an $n\times n$ matrix (real and non-singular) with eigenvalues $\lambda_1,\ldots,\lambda_n$, then the eigenvalues of $A+cI$ are $\lambda_1+c,\ldots,\lambda_n+c$.

My question is on the condition number of $A+cI$, can this also be expressed in terms of the condition number of $A$? We have $$\kappa(A)=\sqrt{\frac{\lambda_{\mathrm{max}}\left(A^TA\right)}{\lambda_{\mathrm{min}}\left(A^TA\right)}},$$ so $$\kappa(A+cI)=\sqrt{\frac{\lambda_{\mathrm{max}}\Big((A+cI)^T(A+cI)\Big)}{\lambda_{\mathrm{min}}\Big((A+cI)^T(A+cI)\Big)}}.$$ Now of course $\lambda(A)=\lambda(A^T)$, but is there a relation between $\lambda(A)$ and $\lambda(A^TA)$? That is really all that I'm missing to connect $\kappa(A+cI)$ with $\kappa(A)$.


Edit I'll restate my question, as the current answer is not what I was looking for. I am not necessarily looking for a relation of the form $\kappa(A+cI)=f(\kappa(A))$ for some function $f$, since that apparently does not exist.

What I hope does exist, is a relation between $\lambda(A)$ and $\lambda(A^TA)$, such that I can rewrite the above and arrive at some relation between $\kappa(A)$ and $\kappa(A+cI)$. So, does that exist?

For example when $A$ is SPD, $$\kappa(A)=\frac{\lambda_{\mathrm{max}}(A)}{\lambda_{\mathrm{min}}(A)}\quad \mbox{ and }\quad \kappa(A+cI)=\frac{\lambda_{\mathrm{max}}(A)+c}{\lambda_{\mathrm{min}}(A)+c}$$ and $$\kappa(A)<\kappa(A+cI)\quad \mathrm{ or } \quad \kappa(A)>\kappa(A+cI) $$ depending on $c$. Now I was wondering if similar results could be derived for general $A$.

$\endgroup$
4
  • $\begingroup$ I was ready to bet that the eigenvalues of $A^TA$ were $|\lambda_j|^2$, $\{\lambda_j\}$ being the eigenvalues of $A$, but unfortunately I realized it is not true. The matrix $A=\begin{bmatrix} 0 &1 \\ 0 & 0 \end{bmatrix}$ only has $0$ as an eigenvalue but $A^TA=\begin{bmatrix} 0 & 0 \\ 0 & 1\end{bmatrix}$ has the unexpected eigenvalue $1$. $\endgroup$ Feb 3, 2016 at 9:33
  • 1
    $\begingroup$ That is only true for symmetric $A$, since then $A^TA=A^2$ $\endgroup$
    – Eric S.
    Feb 3, 2016 at 9:34
  • $\begingroup$ This might be true for normal matrices, however. $\endgroup$ Feb 3, 2016 at 9:34
  • $\begingroup$ Didn't see your comment. I agree. This must be true for normal matrices (i.e., $A^TA=AA^T$), which include symmetric ones. P.S. Yes, it is true. If $A$ is normal then $A=U\rm{diag}(\lambda_j)U^\star$, where ${}^\star$ means "conjugate and transpose" and $U$ is unitary. So in particular $A^T=U\rm{diag}(\overline{\lambda_j})U^\star$ and one has that $A^TA$ has $|\lambda_j|^2$ as eigenvalues. HTH $\endgroup$ Feb 3, 2016 at 9:35

2 Answers 2

1
$\begingroup$

Condition number depends primarily on singular values of $A$. (which are the eigenvalues of $A^TA$) Adding $cI$ can be described simply as a modification on eigenvalues.

In order to modify singular values of $A$, you need to add $UcIV=cUV$, if $A=U D_{iag}(s_i) V$ is the singular value decomposition.

I think this reflects the difficulty of expressing simply the Condition number of $A+cI$.

(For real symmetric matrices $V=U^T$, for condition number of complex matrices, I guess you should use $A^*A$ instead of $A^TA$. Are the problem restricted to matrixes with real elements?)

Response to the edited question:
If $A=U D V$, where $D=D_{iag}(s_i)$, then $A^TA=V^T D U^TU D V=V^TD^2V$.
If you add $cI$ to A, then
$(A+cI)=UDV+cI=U(D+cU^T V^T)V$, and
$(A+cI)^T(A+cI)=V^T (D^T+cVU)(D+cU^T V^T) V $ so the further $VU$ is from being diagonal, the further your singular values might fall from $s_i+c$.

I am expecting that there is no exact formulation, but you can vizualise the change of condition number numerically with random matrices, starting from symmetric ones, and adding small amount $\mu$ of non-symmetric part.
$A'=B+\mu C$, $B=1/2(A+A^T)$, $C=-1/2 (A-A^T)$.

$\endgroup$
3
  • $\begingroup$ Yes, the matrices are real. No offense intended, but how does your answer answer my question? $\endgroup$
    – Eric S.
    Feb 3, 2016 at 14:24
  • $\begingroup$ The hypothesis is that there might be a relatively simple formula $\endgroup$ Feb 3, 2016 at 20:47
  • $\begingroup$ You can verify this hypothesis by numeric examples. My guess is that there is no exact formula, however, if your question arise from a given problem, and your matrices are somehow special, You might find some upper-lower limits. Maybe Gersgorin-circles can be used... Adding $I$ to the 2x2 90 degree rotation matrix $R$, the singular values change from $1,1$ to $\sqrt 2,\sqrt 2$. $\endgroup$ Feb 3, 2016 at 20:58
0
$\begingroup$

You cannot express $\kappa(A+cI)$ in terms of $\kappa(A)$ independently of the individual eigenvalues. For example let $$A_{r,s}=\left(\begin{matrix} r&0\\ 0&s\\ \end{matrix}\right)$$ with $0<s<r$ so that $\kappa(A_{r,s})=\frac r s.$

For fixed $c$ and $\alpha>1$ the expression $\kappa(A_{r,s}+cI)=\frac{r+c}{s+c}$ is nonconstant along the line $r=\alpha s;$ therefore it cannot be written as some function $f(\frac r s,c).$

$\endgroup$
5
  • $\begingroup$ Expressing it dependent on the individual eigenvalues is fine with me. $\endgroup$
    – Eric S.
    Feb 3, 2016 at 9:29
  • $\begingroup$ "My question is [...] can this also be expressed in terms of the condition number of $A$?" If you write an expression involving individual eigenvalues then you no longer need to mention the condition number of $A$ because that is just another quotient of eigenvalues. $\endgroup$ Feb 3, 2016 at 9:30
  • $\begingroup$ Yes but when I asked "My question is [...] can this also be expressed in terms of the condition number of $A$?" I had not read your answer yet. When I did read your answer, I thought: "Okay, so it is not possible, maybe it is possible to express it in terms of eigenvalues", which sparked my comment... $\endgroup$
    – Eric S.
    Feb 3, 2016 at 9:36
  • $\begingroup$ Fair enough. If $A$ is normal then you can perform all kinds of functions on $A,$ including rational functions, taking the absolute value, and even a properly defined square root, resulting in another normal matrix whose eigenvalues can be obtained by applying the same functions on the original eigenvalues. $\endgroup$ Feb 3, 2016 at 9:49
  • $\begingroup$ I've updated my question, as your answer does not satisfy me. $\endgroup$
    – Eric S.
    Feb 3, 2016 at 12:41

You must log in to answer this question.

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