Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
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}$. –  Omnomnomnom Jul 28 at 20:23
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? –  Omnomnomnom Jul 28 at 20:29

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
+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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.