Let \(G\) be a connected reductive group with maximal torus \(T\) and Borel subgroup \(B\) containing \(T\). Let \(N = N_G(T)\) and let \(W = N / T\) be the Weyl group. The Bruhat decomposition of \(G\) (see [1, Theorem 14.12]) is \[\begin{equation*} G = \bigsqcup_{w \in W} B w B \end{equation*}\]

Computing the Bruhat Decomposition

In the case \(\DeclareMathOperator{\GL}{GL} G = \GL_n\), we can take \(B\) to be the subgroup of upper triangular matrices, and \(W \cong S_n\). The Bruhat decomposition then asserts that for any \(A \in \GL_n\), there is a permutation matrix \(P\) and upper triangular matrices \(U_1, U_2\) such that \[\begin{equation*} A = U_1 P U_2 \end{equation*}\] We can use an algorithm very similar to the \(LU\)-decomposition to compute a Bruhat decomposition. We want \(U_1^{-1} A = P U_2\). In row-reducing \(A\), we search for a pivot starting from the bottom row of \(A\) and add multiples of it to the rows above. For example, suppose \[\begin{equation*} A = \begin{pmatrix} 3 & -1 & -3 \\ \color{red}{1} & -2 & 1 \\ 0 & 1 & 2 \end{pmatrix} \end{equation*}\] The pivot is colored in red. We use it to eliminate the \(3\) above, to get \[\begin{equation*} \begin{pmatrix} 0 & 5 & -6 \\ \color{red}{1} & -2 & 1 \\ 0 & \color{red}{1} & 2 \end{pmatrix} \end{equation*}\] Moving onto the second column, the new pivot is the \(1\) in the bottom row. We use this to eliminate the \(5\) in the first row. (We can ignore rows with pivots.) This gives \[\begin{equation*} P U_2 = \begin{pmatrix} 0 & 0 & \color{red}{-16} \\ \color{red}{1} & -2 & 1 \\ 0 & \color{red}{1} & 2 \end{pmatrix} \end{equation*}\] We record the (inverses of) operations performed above in \(U_1\): \[\begin{equation*} U_1^{-1} = \begin{pmatrix} 1 & & -5 \\ & 1 & \\ & & 1 \end{pmatrix} \begin{pmatrix} 1 & -3 & \\ & 1 & \\ & & 1 \end{pmatrix} \end{equation*}\] We find \(P\) such that the pivots (red entries) are on the diagonal. This gives \[\begin{equation*} U_1 = \begin{pmatrix} 1 & 3 & 5 \\ & 1 & 0 \\ & & 1 \end{pmatrix} ,\qquad P = \begin{pmatrix} & & 1 \\ 1 & & \\ & 1 & \end{pmatrix} ,\qquad U_2 = \begin{pmatrix} 1 & -2 & 1 \\ & 1 & 2 \\ & & -16 \end{pmatrix} \end{equation*}\] This gives the Bruhat decomposition for \(A\).

Bruhat Cells

Let \(G\) be a connected reductive group. There is an ordering on the Weyl group \(W\) (or more generally any Coxeter group), called the Bruhat order. We have \(u \le v\) if and only if some reduced expression for \(u\) is a subsequence of a reduced expression for \(v\) (see [3, Theorem 2.2.2]). It turns out that this ordering is conencted to the geometry of the Bruhat cells \(BwB\). Namely, \[\begin{equation*} \overline{BwB} = \bigsqcup_{v \le w}{BvB} \end{equation*}\] (see [2, Proposition 3.2.8]). In other words, the Bruhat order is related to inclusions of \(\overline{BwB}\).

Let’s consider a special case of this. Let \(w_0\) be the longest element of \(W\). Then for any \(w \in W\), we have \(w \le w_0\) (see the proof of [2, Proposition 2.1.5]). Then we have \(G = \overline{B w_0 B}\). In the case \(G = \GL_n\), this says the set of matrices \(A\) with an \(LU\)-decomposition \(A = LU\) is (Zariski) dense. Indeed, \(w_0\) in this case is \[\begin{equation*} w_0 = \begin{pmatrix} & & 1 \\ & \mathinner{ \kern 1mu\raise 1pt{.} \kern 2mu\raise 4pt{.} \kern 2mu\raise 7pt{\Rule{0pt}{7pt}{0pt}.} \kern 1mu }& \\ 1 & & \end{pmatrix} \end{equation*}\] and \(w_0 B w_0\) is the subgroup of lower triangular matrices. \(G = \overline{(w_0 B w_0) B}\).

References

[1] Armand Borel, Linear Algebraic Groups, Second Enlarged Edition

[2] Francois Digne and Jean Michel, Representations of Finite Groups of Lie Type

[3] Anders Bjorner and Francesco Brenti, Combinatorics of Coxeter Groups