6
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

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