I'm wondering about which bounds one can put on the condition number of a $n\times n$ square matrix which is obtained from another $n\times n$ square matrix by orthogonalizing the first $m < n$ columns. Obviously, the condition number will become 1 if $m = n$ (and hence minimal). I am wondering whether the condition number is always improving, even if only a few columns are orthogonalized. If this is not the case, I would also be happy to know whether one can put a bound on how much the condition number can become worse.

To be more specific, I have a $n \times n$ matrix \[A = (A_0\, |\, A_1)\] with $A_0 = Q\,R$ with $Q$ a $n \times m$ unitary matrix and $R$ an $m\times m$ upper triangular matrix, $m\leq n$. The columns of $A_0$ can be assumed to be normalized to 1, $||A(:,i)||_p = 1$ for $i = 1 \dots n$. (If it helps, one can also assume the columns of $A_1$ to be normalized to unity).

I now define \[A' = (Q\,|\,A_1).\] The condition number in the $p$-norm is defined as $\kappa_p(A) = ||A||_p \,||A^{-1}||_p$.

Is it possible to give an upper bound on $\kappa_p(A')$ compared to $\kappa_p(A)$? (for example, does $\kappa_p(A') \leq \kappa_p(A)$ hold? [probably not, see below])

## Background

The problem arises in the numerical solution of a quantum mechanical scattering problem where we have to solve an ordinary linear system. The columns of $A_0$ are given by the eigenvectors of a different problem that describes modes that are coupled out and in of the system; the matrix $A_1$ corresponds to the scatterer and is in principle unrelated to $A_0$. (There is a lot of additional structure in the problem, but that is probably too special for mathoverflow). It turns out that sometimes the eigenvectors forming $A_0$ are numerically almost linearly dependent (they are eigenvectors of a general eigenproblem, not Hermitian).

We were able to reformulate the physical question such that instead of putting in the eigenvectors explicitely in $A_0$ we could use an orthogonal basis spanning the space of eigenvectors, which we can easily find using the Schur form of the eigenproblem. This allows us to write $A_0 = Q R$ as described above (and we actually do not need to worry about accuracy in this step).

Now, if the whole matrix $A$ is ill-conditioned because of nearly linearly dependen vectors in $A_0$, going to $A'$ will certainly improve the condition number drastically. I am wondering if this step however can also do harm, if we always apply it, regardless of the condition of $A_0$.

## Attempts of mine so far

Numerical tests on random, ill-conditioned matrices (constructed via SVD) have shown that if I orthogonalize a few columns, the condition number does not get much better, but also not much worse. However, I saw examples where it did get somewhat worse (10-20% larger condition number), hence $\kappa_p(A') \leq \kappa_p(A)$ is probably not true.

With $A = A' \begin{pmatrix}R &0\\\\0&1\end{pmatrix}$, and since $\kappa_2(\begin{pmatrix}R &0\\\\0&1\end{pmatrix})=\kappa_2(R)$ (the largest singular value of R is $||R||_2 \geq \max_i ||R(:,i)||_2=1$) I can find the bounds $\kappa_2(A)/\kappa_2(R) \leq \kappa_2(A') \leq \kappa_2(A) \kappa_2(R)$. This tells me that if $A_0$ is well-conditioned, the condition number of $A'$ is similar to $A$, but the bounds are way to loose if $A_0$ has nearly linearly dependent columns (where the orthogonalization helps most. Not surprising, as I wasn't able to use that fact that $Q$ is orthogonal.)

definitelynot true? Or are you simply leaving open the possibility that the numerics are highly inaccurate? $\endgroup$ – Mark Meckes Jul 6 '13 at 10:53