2

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?

user64494
  • 5,811
  • 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. – Ben Grossmann Jul 28 '14 at 20:10
  • @angryavian if that were the case, then $A$ would be invertible in practice if and only if it were invertible – Ben Grossmann Jul 28 '14 at 20:13
  • @ Omnomnomnom: Why do you think so? – user64494 Jul 28 '14 at 20:13
  • @ Omnomnomnom: How about $ n>10^{10}$? – user64494 Jul 28 '14 at 20:22
  • 1
    (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}$. – Ben Grossmann Jul 28 '14 at 20:23
  • For $n \geq 10^{10}$, we can get an non-invertible matrix that is invertible in practice by subtracting $10^{-10}$ from each entry of the identity matrix. – Ben Grossmann Jul 28 '14 at 20:26
  • @ Omnomnomnom: Can you elaborate your suggestion? – user64494 Jul 28 '14 at 20:28
  • 1
    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? – Ben Grossmann Jul 28 '14 at 20:29
  • @ Omnomnomnom: Please convert your comment to your answer. I would like my question was rightly answered. Of course, $10^{10}$ is too big, the one may be replaced by $10^4$, say. – user64494 Jul 28 '14 at 20:36

2 Answers2

3

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

Ben Grossmann
  • 225,327
1

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
  • 49,280