Easy way of checking for matrix invertability?

[rayver]

Easy way of checking for matrix invertability?

Hi everyone,

I'm designing a particular algorithm and part of it requires to check if a given Matrix is invertible or not. Computation of the actual determinant is not necessary.

So far I've been doing it with a LU factorization, and then checking for zeros in the diagonal of matrix U, but I was wondering if there is a computationally easier way of doing it. I need to run my algorithm many times (possibly billions) so the less steps it takes the better.

Any ideas?

By the way, just so you know, the algorithm uses only binary matrices (their elements are only 1s and 0s) and matrices full of zeros are allowed.

Thanks.

Daniel @EPFL

 

[arildno]

Well, I'm not sure you <i>can</i> determine invertibility of a matrix much faster than you already have tried, but here's a thought:
Since a non-invertible matrix essentially has a reduced span, you might possibly devise an algorithm to check whether the images of unit base vectors forms a linearly independent set or not (the latter implying non-invertibility).
However, this is most likely ending up calculating the determinant rather than being a step in the right direction...

 

[rayver]

Well, I'm not sure you <i>can</i> determine invertibility of a matrix much faster than you already have tried, but here's a thought:
Since a non-invertible matrix essentially has a reduced span, you might possibly devise an algorithm to check whether the images of unit base vectors forms a linearly independent set or not (the latter implying non-invertibility).
However, this is most likely ending up calculating the determinant rather than being a step in the right direction...

Thanks, I sort of tried that already by calculating the rank of the matrix through the Singular Value Decomposition method and then comparing it with the size of the matrix. As it turns out, the SVD algorithm is computationally much heavier than the LU algorithm.

I wonder if there exist some sort of theorem or identity that might help me with this.
Also, the matrix is a block matrix, this is, it is a square matrix of size 2K composed of 4 smaller matrices of size K. Is this any useful?

C´mon mathematicians, don´t disappoint me!

Daniel @EPFL

 

[Gib Z]

$$I - B$$ is invertible if $$||B||<1$$ where $$||B|| = \sqrt{ \sum_{i=1}^{m} \sum_{j=1}^{n} |b_{ij}|^2}$$ is the Matrix Norm, and the Inverse will be given by $$(I-B)^{-1} = \sum_{k=0}^{\infty} B^k$$