ULU Decomposition of a matrix Let $g \in GL_n(\mathbb{F}_q)$. Is it true that we can always write $g = u_1lu_2$, where $u_1$ and $u_2$ are upper-triangular and $l$ is lower-triangular? Note that I'm not requiring that the matrices be unipotent.
This is equivalent to being able to write $g=u_1lu_2d$, where $u_1$ and $u_2$ are unipotent upper-triangular, $l$ is unipotent lower-triangular, and $d$ is a diagonal matrix (see Geoff's comment below).
Remark: It suffices to show that this is true for $g$ a permutation matrix; the Bruhat decomposition will then guarantee that this will be true for arbitrary $g$. In particular, the statement is true for $n=2$ as
$$
     \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}\begin{pmatrix} 1 & 0 \\ -1 & 1 \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}\begin{pmatrix} -1 & 0 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}.
$$
 A: To atone for my misguided earlier attempt at an answer, I'd suggest a different way to get a general criterion of this sort (working first over an algebraically closed field, then adapting to finite fields via the BN-pair structure).    While this is less elementary than the matrix theory over rings involved in the treatment of general linear groups, it explains the result conceptually in terms of the Bruhat decomposition.   (Recall that this decomposition is a natural generalization to reductive groups of Gauss reduction in elementary linear algebra.)
The ideas here all go back to the 1956-58 Chevalley seminar, but the three textbooks Linear Algebraic Groups by Borel, Springer, and myself may be easier to refer to.    In a connected semisimple (or reductive) algebraic group $G$, the Borel subgroups are all conjugate, so we can fix a particular $B$.   Working in $G$ or in the (projective) flag variety $G/B$, we get a disjoint decomposition indexed by elements of the Weyl group $W$, starting with $G= \bigcup_w BwB$.
In the resulting Bruhat cell decomposition of $G/B$, the cell corresponding to $w \in W$ is isomorphic to an affine space of dimension $\ell(w)$.   Then the longest element $w_\circ$ of $W$ (of length $= \dim G/B$, the number of positive roots) yields a dense open subset.   The double coset $Bw_\circ B$ is similarly a dense open subset of $G$.   Its left translate $\Omega:=w_\circ B w_\circ B$ is often called the big cell in $G$; it is in fact a principal open set in $G$.    
Relative to a fixed maximal torus lying in $B$, we have $B = TU$ with $U$ maximal unipotent.  Similarly $B^- := w_\circ B w_\circ = TU^-$.  (Note that $w_\circ$ is its own inverse.)  Here $U, U^-$ would be the upper and lower triangular unipotent matrices in the general linear group.   Now recall a trivial lemma (7.4 in my book): the product of two nonempty Zariski-open (hence dense) subsets in $G$ is all of $G$.  Apply this to $Bw_\circ B$, along with the fact that $T$ can be moved past other factors to combine with $B$, to conclude:  $$G = (B w_\circ B) (B w_\circ B) = B w_\circ B w_\circ B = U U^- B.$$    
A: The keyword for this is "Gauss decomposition". It states that for a ring R of stable rank 1 one can indeed write any element g of GL(n,R) as a product of three upper and lower triangular matrices (not unipotent, though). So it holds not only for finite fields, but for any field and, more generally, semilocal ring, along with many other examples such as the ring of all algebraic integers. And for GL one doesn't even require R to be commutative.
I'm having trouble tracing the first appearence of this in the literature (but probably it goes back to the work of Bass), so here are two links:


*

*A paper, where this is proved for any [elementary] Chevalley groups (not extended, but the idea works for them too), and the ring is assumed to be commutative. It also contains an overview of the previous results on the topic;

*Another paper, where this is proved for $GL_n$ over possibly non-commutative rings of stable rank 1.


If you ask the matrices to be unipotent, then, first, you can only get matrices from $SL_n$, and second, three is not enough, the torus is the obstacle. But if you take four upper and lower unipotent triangular matrices, you can do it (still in $SL_n$). For this the keyword is "unitriangular factorisation".
