Is the decomposition of a matrix as product of elementary matrices unique? We know that an invertible matrix $A$ can be written as a product of elementary matrices, say $E_1\cdots E_n$. This decomposition is, clearly, not unique. For example, the elementary matrix $M$ that exchanges row 1 and row 2 can be inserted in the product an even number of times like this:
$$E_1MMMME_2\cdots E_n$$
We also know that an elementary decomposition can be found by doing row operations on the matrix to find its inverse, and taking the inverses of those elementary matrices. Suppose we are using the most efficient method to find the inverse, by most efficient I mean the least number of steps:


*

*Is the resulting decomposition unique? Put another way, is the most efficient method unique? (I suspect it is not.)

*Is the resulting decomposition unique up to the ordering of the matrices? (I suspect it is in the case of $2\times 2$ matrices, and it isn't in matrices of higher dimensions)

*Failing those two questions to be true, there must be some uniqueness because the determinant of the matrix is unique. What could it be?
 A: Let $$A=\pmatrix{2&3\cr4&5\cr}$$ (for example – almost any example should do). You could divide the first row by 2; subtract 4 times the first row from the second; divide the second row by the appropriate number (to get a 1 in the lower right corner); subtract the appropriate multiple of the second row from the first. 
Or, you could divide the second row by 5; subtract 3 times the second row from the first; divide the first row by the appropriate number; subtract the appropriate multiple of the first row from the second. 
Either way, you get (efficiently) a factorization into four elementary matrices, but they are different factorizations, even if reordering the matrices is allowed. 
EDIT: More simply, one could just note that $$\pmatrix{a&0\cr0&1\cr}\pmatrix{1&b\cr0&1\cr}=\pmatrix{1&ab\cr0&1\cr}\pmatrix{a&0\cr0&1\cr}$$
A: The factorization of a permutation as a product of transpositions is not unique:
$$(1\ 2\ 3)=(1\ 2)(2\ 3)=(1\ 3)(1\ 2)=(2\ 3)(1\ 3).$$
Likewise, the factorization of a permutation matrix as a product of elementary permutation matrices is not unique:
$$\left(\begin{matrix}0 & 0 & 1\\1 & 0 & 0\\0 & 1 & 0\end{matrix}\right)=$$$$\left(\begin{matrix}0 & 1 & 0\\1 & 0 & 0\\0 & 0 & 1\end{matrix}\right)\left(\begin{matrix}1 & 0 & 0\\0 & 0 & 1\\0 & 1 & 0\end{matrix}\right)=\left(\begin{matrix} 0 & 0 & 1\\0 & 1 & 0\\1 & 0 & 0\end{matrix}\right)\left(\begin{matrix} 0 & 1 & 0\\1 & 0 & 0\\0 & 0 & 1\end{matrix}\right)=\left(\begin{matrix} 1 & 0 & 0\\0 & 0 & 1\\0 & 1 & 0\end{matrix}\right)\left(\begin{matrix} 0 & 0 & 1\\0 & 1 & 0\\1 & 0 & 0\end{matrix}\right).$$
