Minimum Elementary row/column transformations to find Inverse of given Matric

Question

While working out some elementary transformation to find Inverse of matrix, it get in my mind,

what is the minimum number of elementary transformations needed to find the inverse of a matrix?

---

Editor's note: see Finding the inverse of a matrix by elementary transformations. for the method of elementary transformation

EDIT. Here is a detailed description of the studied issue. We are interested in the inversion of matrices, defined on a field (finite or not), by methods of Gauss type; we know the maximum complexity of these methods. We ask which are the matrices whose inversion requires the complete progress of the algorithm; in particular, do we find ourselves in the worst case almost always?

Answer 1

Let $(d_i)_{i\leq n}$ be the leading principal minors of the considered complex $n\times n$ matrix $A\in M_n$.

The decomposition $A=LU$ exists and is unique iff for every $i$ $d_i\not=0$. This is equivalent to say that, in these conditions, the calculation of $A^{-1}$ can be done ( using Gauss Jordan) without any permutation. In fact, after the $n(n-1)$ linear combinations of rows or columns, $A$ is " diagonalized" in the form $(*)$ $diag(d_1,d_2/d_1,d_3/d_2,\cdots)$.

Here we admit permutations ($A=PLU$).

Let $Z=\{M\in M_n;\text{all minors of} \;M \;\text{are invertible}\}$. Note that the number of algebraic conditions in the definition of $Z$ is great but finite.

Then $Z$ is an algebraic set that is non-void (choose for the $(a_{i,j})$ algebraically independent complex numbers) and Zariski open. In particular, $M_n\setminus Z$ is Zariski closed and has $0$ Lebesgue measure; moreover, if the $(a_{i,j})$ follow a normal law, then the probability that a randomly chosen matrix $A$ is in $Z$ is equal to $1$.

It is not difficult to see that, if $A$ is a generic matrix, in the sense $A\in Z$, then you cannot reduce the number of $ n( n-1)$ linear combinations; indeed, at each step, the entries of the matrix are either $0$ by construction or product-fractions of determinants of minors of $A$.

For the same reason, the normalization of the diagonal matrix $(*)$ generically needs $n$ steps (Add some algebraic conditions in the definition of $Z$).

Answer 2

For another variation on it, here's the finite field case:

For sufficiently large prime powers $q$, there are some matrices in $GL_n(\mathbb{F}_q)$ that cannot be written as a product of fewer than $n^2$ elementary matrices. This is equivalent to reducing to the identity in fewer than $n$ steps, by the simple process of taking the inverse.

How many elementary matrices are there? $\binom{n}{2}$ row swaps, $n(n-1)(q-1)$ ways to add a multiple of a row to another row, $n(q-2)$ ways to multiply a row by a nontrivial constant, and the identity (we leave that in so that we can pad out shorter sequences). For $n\ge 2$, that's $n^2(q-1)+\frac{n^2-n}{2}-n+1 < n^2q$ total elementary matrices.

Now, a crude estimate. There are less than $(n^2q)^{n^2-1}$ ordered products of $n^2-1$ elementary matrices, and there are $(q^n-1)(q^n-q)\cdots (q^n-q^{n-1}) > q^{n^2}\cdot (1-\frac1q)^n$ invertible matrices. We have $$(n^2q)^{n^2-1} = n^{2n^2-2}q^{n^2-1} = q^{n^2}\cdot \frac{n^{2n^2-2}}{q} \le q^{n^2}\cdot \frac{q-n}{q} < q^{n^2}\cdot \left(1-\frac1q\right)^n$$ as long as $q\ge n+n^{2n^2-2}$ for that critical $\le$ step. As I said, sufficiently large $q$. For $n=2$, this says that any field with at least $66$ elements will require us to use the full four operations to cover everything.

This is a very crude estimate, of course. There are certainly many smaller fields that require all of the steps to reach everything. However, not all fields do. For example, consider $2\times 2$ matrices over $\mathbb{F}_2$. There are six invertible matrices, which form a group isomorphic to $S_3$. There are three elementary matrices other than the identity - the three elements of order $2$ in that group. Every element in the group can be written as a product of one or two of them.

Answer 3

Interesting question! The following is not an answer, rather an extended comment, unfortunately.

If you follow the standard procedure of Gauss-Jordan Elimination of an invertible $n \times n$ matrix, we can get a plausible upper bound:

1. If the top left entry is $0$, then swap it with a non-zero entry in the first column (note, if the matrix is invertible, there must be such an entry).
2. Often, now would be a good time to divide the row by the leading entry, so that it becomes $1$, but this will just slow us down!
3. Subtract a multiple of the first row from each other row, so that the leading entry becomes $0$. Note that, if there was a $0$ in the top left corner, it is now elsewhere, causing us to be able to skip one of these operations!
4. Repeat this, essentially, for the next column, more or less ignoring the first column, and trying to put a single pivot in the second entry in the diagonal of the matrix. This is a good time to ensure there are $0$s above your pivots too, requiring always a maximum of $n - 1$ operations.
5. Now, your matrix is diagonal. Time to divide rows by the diagonal entries, requiring at most $n$ operations.

So, every invertible $n \times n$ matrix can be reduced to the identity in $n(n - 1) + n = n^2$ steps, at which point, if you've augmented the identity matrix onto your matrix, the augmented columns become the inverse matrix.

Obviously some matrices are much quicker than that (e.g. the identity take no steps!). But, an interesting question would be whether there are matrices that take a full $n^2$ steps. That is, there's no clever combination of $n^2 - 1$ or fewer elementary row matrices that will multiply to give the given matrix.

I suspect that there is one (and probably "most" matrices will be examples), but I'm just not sure what kind of invariants the set of matrices that are generated by at most $n^2 - 1$ elementary row matrices has.