2
$\begingroup$

Let $A$ be a diagonalizable matrix, i.e., $A=X D X^{-1}$. Recall that columns of $X$ correspond to eigenvectors of $A$, and the diagonal entries of the diagonal matrix $D$ correspond to its eigenvalues.

Suppose that $A$ is strictly row/column dominant. In particular assume that $A_{ii}\geq \sum_{j\neq i} |A_{ij}| + c$ for some $c>0$. Similarly for the column sums.

Is it possible to choose $X$ such that the condition number of $X$ is bounded, i.e., can we choose $X$ such that $\kappa(X)= \|X\|_2 \times \|X^{-1}\|_2$ is bounded (e.g., in terms of $c$)?

$\endgroup$
  • $\begingroup$ Recall that the eigenvectors corresponding to distinct eigenvalues are orthogonal to each other and that in situations where there are repeated eigenvalues you can select the eigenvectors so that they're orthogonal. In those situations, the condition number of $X$ is 1. However, you can also choose the eigenvectors stupidly. Let $D=I$ and let $X$ be a very badly conditioned matrix. What happens then? $\endgroup$ – Brian Borchers Oct 10 '17 at 23:17
  • $\begingroup$ Good point! I guess for my purposes the question is whether it is always possible to choose X such that $\kappa(X)$ is small. I'll update the question accordingly. By the way, I'm not assuming that the matrix is symmetric. So, it is not always possible to choose an orthogonal vectors. $\endgroup$ – Ozzy Oct 10 '17 at 23:22
  • $\begingroup$ @BrianBorchers Why should the eigenvectors be orthogonal? There's nothing about $A$ being normal, real symmetric, complex Hermitian, etc. The only assumption here is that $A$ is diagonalizable. $\endgroup$ – Algebraic Pavel Oct 10 '17 at 23:34
  • $\begingroup$ Are you willing to allow for arbitrary scaling of the columns of $X$, or should the columns of $X$ be normalized so that each eigenvector has norm 1? $\endgroup$ – Brian Borchers Oct 11 '17 at 1:05
  • $\begingroup$ Does the result depend on whether the scalings are allowed? If so, suppose that we allow them. $\endgroup$ – Ozzy Oct 11 '17 at 1:15
2
+50
$\begingroup$

No, take for $\epsilon>0$ small: $$ \left(\begin{matrix} 1 & \epsilon \\ 0 & 1 + \epsilon^2 \end{matrix}\right)$$ Eigenvalues $1$ and $1+\epsilon^2$ corresponds to eigenvectors $$ \left(\begin{matrix} 1 \\ 0 \end{matrix}\right) \; \; \mbox{and} \; \; \left(\begin{matrix} 1/\epsilon \\ 1 \end{matrix}\right),$$ respectively. The matrix $X$ has, up to a global scaling (irrelevant for the condition number), the form : $$ X = \left(\begin{matrix} 1 & t/\epsilon \\ 0 & t \end{matrix}\right)$$ for some $t\neq 0$ and then $$ X^{-1} = \left(\begin{matrix} 1 & -1/\epsilon \\ 0 & 1/t \end{matrix}\right)$$ Calculating lower bounds for the eigenvalues of $X^* X$ and $(X^{-1})^* X^{-1}$ and simplifying we see that the condition number is bounded from below by: $$ C \geq \frac{1}{2} \left(\frac{1}{t}+t + \frac{t}{\epsilon^2}\right) $$ which has a minimum for $t=\epsilon$. We conclude that $ C(X)\geq \frac{1}{\epsilon} + \frac{\epsilon}2$ whatever choice you make for the diagonalizing matrix $X$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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