Invertibility of uncertain matrix

Question

Given that we start with some $n\times n$ square matrix $A_0$ that is non-singular. We add some perturbation to it, $\Delta A$, so that our new matrix is $A = A_0 + \Delta A$. The question is whether we can guarantee invertibility of our new $A$ matrix if $|\Delta A_{ij}|<\rho$. We can refer to this $\rho$ as the radius of invertibility or radius of non-singularity.

There seems to be a paper that talks about this exact problem, the additive case: http://www.eecs.berkeley.edu/~elghaoui/Pubs/InvErr_LAA02. It says that $\rho$ is the smallest singular value of $A$.

My question is, if we generate some random $A$ matrix that invertible, can we experimentally converge on $\rho$ through numerous trials? I suppose this is more of a question about possible algorithms than linear algebra.

Answer 1

Actually, if $A=A_0+\Delta A$, where $A_0$ is invertible, then for all $\Delta A$ such that $\|\Delta A\|_*<\rho$ with $\rho=1/\|A_0^{-1}\|_*$ the matrix $A$ is invertible as well. This holds for any sub-multiplicative matrix norm $\|\cdot\|_*$ consistent with some given (but more or less arbitrary) vector norm $\|\cdot\|$, that is, $\|Ax\|\leq\|A\|_*\|x\|$. Note that $\|\cdot\|_*$ does not necessarily need to be the operator norm induced by the vector norm $\|\cdot\|$. That is, all matrices $A$ in an open ball centred at $A_0$ with the radius $\rho$ are invertible. The shape of the ball depends on the choice of the norm $\|\cdot\|_*$.

Indeed, for the 2-norm, that is, $\|\cdot\|_*=\|\cdot\|_2$, $\rho=1/\|A_0^{-1}\|_2=\sigma_{\min}(A_0)$.

Since the set of invertible matrices is dense, it is not likely that a randomly generated matrix will be singular. However, one can simply compute or estimate $\rho$ from the given $A_0$ and the chosen norm using $\rho=\|A_0^{-1}\|_*$. Since for any $x\neq 0$, $\|A_0^{-1}\|_*\leq\|A_0^{-1}x\|/\|x\|=\|y\|/\|A_0y\|$ with $y=A_0^{-1}x$, one can estimate $\|A_0^{-1}\|_*$ by a procedure which attempts to maximise the quotient $\|y\|/\|A_0y\|$ over all nonzero $y$.

Again, for the 2-norm, this might lead to a sort of inverse iteration applied to $A_0^TA_0$.

---

Proof of the first statement: Let $A_0$ be invertible and let $\|\cdot\|_*$ be a sub-multiplicative matrix norm consistent with some vector norm $\|\cdot\|$. Assume that $A=A_0+\Delta A$ is singular. There exists a nonzero vector $x$ such that $0=Ax=A_0x+\Delta A x$, that is, $x=-A_0^{-1}\Delta A x$. Hence $\|x\|=\|A_0^{-1}Ax\|\leq\|A_0^{-1}\|_*\|A\|_*\|x\|$ and therefore dividing by $\|x\|\neq 0$ gives $\|A\|_*\geq 1/\|A_0^{-1}\|_*=\rho$. Since $A_0+\Delta A$ being singular implies that $\|\Delta A\|\geq\rho$, by reversing the implication, we get that if $\|\Delta A\|<\rho$ then $A=A_0+\Delta A$ is nonsingular.

Answer 2

Since determinant is a polynomial (in matrix entries), it's a continuous map, so its inverse maps open sets on open sets (given a norm on matrices, but they are all equivalent, since we are in finite dimension). Since $\Bbb R - \{0\}$ is open, so is the set of invertible matrices (which is simply $\det^{-1}(\Bbb R - \{ 0 \})$). Hence, given a non-singular matrix A, you can find a "ball" of matrices around A that contains only nonsingular matrices. So the answer to your first question is, yes, we can :-)

Regarding the second question, notice first that $\rho$ depends on your matrix norm. Let's take $||A||=\max |a_{i\,j}|$. Then $\rho$ is certainly not greater than (the absolute value of) the smallest eigenvalue of $A$, since $\det(A - \lambda_{min}I) = 0$.

I tried this: compute SVD of $A$ as $A = U D V^T$. Then compute $B=U(D-tI)V^T$, where $t$ is the smallest singular value of $A$.

Thus, $B$ is singular by design (its smallest singular value is $0$). And singular values of $A-B$ are all equal to $t$, since $A-B=U(tI)V^T$.

So you have a $\Delta A = B-A$, such that $A+\Delta A$ is singular, and the spectral norm of $\Delta A$ is the minimum singular value of $A$.