Condition number for matrix of eigenvectors of a diagonally dominant matrix

1.1k Views Asked by At

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$)?

1

There are 1 best solutions below

0
On BEST ANSWER

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