# Why Bruhat decomposition in $GL_n$ case is the Gauss decomposition?

Gauss decomposition of a matrix is also called LU decomposition. Let $A$ be a matrix. Then $A=LU$ for some lower triangular matrix $L$ and upper triangular matrix $U$. This can be obtained using Gauss algorithm.

It is said that Bruhat decomposition in $GL_n$ case is the Gauss decomposition. Why Bruhat decomposition in $GL_n$ case is the Gauss decomposition? Thank you very much.

In the case of $GL_2$. We have Bruhat decomposition $GL_2 = \cup_{w \in W} BwB$, where $W$ is the Weyl group, $B$ is the subgroup of $GL_2$ consisting of all upper triangular matrices.

• Your question is confused. An $LU$ decomposition does not always exists, and a permutation (matrix) is sometimes required in addition. The $w$ in the Bruhat decomposition is essentially that permutation, but you cannot find it in a pure $LU$ decomposition (which only works for matrices in the large Bruhat cell, so I guess $w$ would actually be the longest permutation for this case). – Marc van Leeuwen Jan 14 '14 at 10:39
• @MarcvanLeeuwen, thank you very much. – LJR Jan 14 '14 at 10:42
• The Gauss decomposition is not a special case of Bruhat decomposition. The Gauss decomposition of $G$ is $G=\cup_{w\in W} U^{-}wB$ and the Bruhat decomposition of $G$ is $G=\cup_{w\in W}BwB = \cup_{w\in W}UwB$, where $U$ consists of all unipotent upper triangular matrices and $U^-$ consists of all unipotent lower triangular matrices. – LJR Jan 23 '14 at 11:59
• For the record, we have $U^- = w U w$, so the Gauss decomposition of a matrix $A$ is exactly the Bruhat decomposition of $w A$ and vice versa. – David Loeffler Dec 17 '15 at 12:18
• @David Loeffler, thank you very much. – LJR Dec 17 '15 at 16:33

I will try and write this out in a (little) bit more explicit detail using matrices, as I am sort of studying this too.

Given any matrix $$M$$, we can apply three possible row operations to its rows: multiplying a row by some scalar, adding one row to another, and reordering rows. Each of these rows corresponds to an elementary matrix, and the last operation in particular corresponds to a permutation matrix $$\dot{w}$$.

We know from linear algebra that any matrix can always be transformed using these operations into an upper triangular matrix, so the equation $$g = b_1 w b_2$$ essentially boils down to saying "given any invertible matrix $$g$$, apply $$b_1^{-1}$$ to it (which should multiply and/or add rows), then apply $$w^{-1}$$ to the result to reorder rows so that you can get an upper triangular matrix $$b_2$$".

The row operation of multiplication of row $$i$$ by $$\lambda$$ has an elementary matrix given by 1s on the diagonal and the $$i$$-th diagonal entry $$\lambda$$. The row operation of adding $$\lambda$$ multiplied by row $$i$$ to row $$j$$ is given by the identity matrix plus a matrix with the $$(j,i)$$ entry being $$\lambda$$ (and zero elsewhere). The wikipedia page sums this up much better than I just did.

If in particular we restrict to only adding 'lower' rows of the matrix to 'higher' rows (that is, we add row $$i$$ to row $$j$$ when $$i > j$$), then the corresponding elementary matrix is an upper triangular matrix.

So, given an invertible matrix $$g$$, we only add lower rows to higher rows, and scale rows, to give a sequence of elementary matrices $$E_1 E_2 \dots E_r$$ (in fact, there are a finite number of the elementary matrices by the invertible matrix theorem). These are all upper triangular, so their product is the required $$b_1^{-1}$$ from before. It's also fine to restrict the row addition operation to only adding lower to higher, since reordering will take care of the rest.

This gives the desired correspondence between Gaussian elimination and the Bruhat decomposition for $$GL_n$$. Since the given echelon form $$b_2$$ is can be reached through an essentially unique order of applying the elementary matrices, this decomposition is also bijective.

As far as I can tell, the actual proof requires an inductive argument (I looked at this SE question and the comments of this MO discussion), but I don't think that's entirely necessary to get the general gist of the Bruhat decomposition for type A. Feedback on my answer is welcome, but I'm pretty sure I've covered the main idea behind this bijection.