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?
Best Answer
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.