# A question about invertible matrices

A square matrix $A$ over the reals is said to be invertible in practice if there exists a matrix $B$ of the same size s. t. all the entries of $AB$ differ from the corresponding entries of the identity matrix $E$ less than or equal to $10^{-10}$. Does there exist invertible in practice marix which is not invertible?

-
If this definition corresponds to how things are done in practice, however, then the set of matrices that are invertible in practice should be a strict subset of the invertible matrices. –  Omnomnomnom Jul 28 at 20:10
@angryavian if that were the case, then $A$ would be invertible in practice if and only if it were invertible –  Omnomnomnom Jul 28 at 20:13
@ Omnomnomnom: Why do you think so? –  user64494 Jul 28 at 20:13
(Retyped): Let $\|\cdot\|$ be the column-sum (or row-sum) norm. Assume we're talking about $n \times n$ matrices. Let $M$ be a matrix such that $|M_{ij} - I_{ij}| \leq 10^{-10}$. Then $\|M - I\| \leq n/{10^{10}}$. It follows that $\sigma(M) \subset [1-n/{10^{10}},1+n/{10^{10}}]$. It follows that $M$ must be invertible as long as $n < 10^{10}$. –  Omnomnomnom Jul 28 at 20:23
Yes, if that's really interesting to you. I would remind you, however, that in discussing $10^{10}\times 10^{10}$-sized matrices, we have deviated drastically from practice. Could you elaborate on the motivation for this definition and this question? –  Omnomnomnom Jul 28 at 20:29

## 2 Answers

The set of $n \times n$ matrices that are "invertible in practice" is exactly the set of $n \times n$ matrices that are invertible, as long as $n < 10^{10}$.

For $n \geq 10^{10}$, invertible matrices are invertible in practice, but not the other way around. For a counterexample, consider the matrix given by $$A_{ij} = \begin{cases} 1 - 1/n & i=j\\ -1/n & i \neq j \end{cases}$$ Noting that the row sums of $A$ are all zero, we may conclude that $A$ is not invertible. Nevertheless, it is "invertible in practice".

-
+1: Nice. We must have $\|A-I\| \ge 1$ for any sub-multiplicative norm. –  copper.hat Jul 28 at 20:44
(My point was that it is curious how dimension plays into sub-multiplicative matrix norms.) –  copper.hat Jul 28 at 21:00
@copper.hat thank you! And agreed; it's one of the many counter-intuitive things about $n$-dimensional space. –  Omnomnomnom Jul 28 at 21:07

Technically, yes, but practically, no.

Technical answer:

Consider the $n\times n$ matrix

$$M = \left[\begin{array}{ccccc}1 & x & x & \ldots & x\\x & 1 & 0 & \ldots & 0\\x & 0 & 1 & \ldots & 0\\ \vdots & & & \ddots & \\ x & 0 & 0 &\ldots & 1\end{array}\right].$$

By row-reduction the determinant of this matrix is $1 - (n-1)x^2$ and in particular, $M$ is singular when $x = \sqrt{1/(n-1)}$. You can make $x$ arbitrary small (in particular, less than $10^{-10}$) by making $n$ arbitrary large; and then if $AB = M$, at least one of $A$ or $B^T$ is singular while being "practically invertible."

Practical answer: suppose your matrix is $n\times n$, where $n < 10^{10}$. Then any matrix $M$ that is close to the identity matrix, in the sense you describe, is strictly diagonally dominant and hence nonsingular. Therefore any $A, B$ with $AB=M$ are both nonsingular as well.

-
@ user7530: +1. The question arises: does there exist a counterexample of a different kind? –  user64494 Jul 28 at 20:47