Matrix decomposition into 2x2 elementary transforms Rotation matrices can be decomposed into a product of $\frac{n(n-1)}{2}$ elementary rotations operating on only two coordinates.
Similarly, can any square matrix be decomposed into a product of $\frac{n(n-1)}{2}$  linear transforms operating on two coordinates only each?
Note: $ n(n-1) $ can be done by reversing Gaussian elimination.
 A: I don’t know how to “prove” the negative, but this answer is intended to provide some additional insight.
Presumably, the comment about a general rotation matrix being decomposable into a product of $n(n-1)/2$ elementary rotations arises from the type of sequential Givens rotation argument provided on the Wikipedia page for rotation matrices (see Decompositions).  What is less well known is that there is a specific (close to unique) butterfly (or lattice) pattern of $n(n-1)/2$ basic Givens rotations associated with any arbitrary orthogonal or unitary matrix – see this link.  This butterfly pattern is precisely the generalization of the FFT (properly scaled, the discrete Fourier transform is a unitary matrix).  Unfortunately, the generalization is not inherently “fast”, but it does expose the symmetries which permit the FFT to be fast, and it suggests (currently unexploited) ways one might design other fast transforms.  The development is specific to   n being an even power of $2$ , but as there are FFT algorithms for radix choices other than $2$ , it is reasonable to assume that the general form similarly extends.
Now any square matrix necessarily possesses an SVD which, when expressed in the form of a flow graph, consists of two of these $n(n-1)/2$ lattices (the left and right singular vector matrices) connected by a set of simple scalar scaling operations (the singular value matrix).  Accounted this way, there are precisely
$$2 \cdot \frac{n(n-1)}2 = n(n-1)$$
$2 \times{ 2} $ linear transforms (all rotations) plus $n$ scalar operations.  It is obvious how one can do slightly better than this, by combining the inner layers of the two lattices with the scalar scaling operations to yield n/2 linear transforms of size 2 x 2 in the middle, so that one is left with a total of
$$2 \cdot \left( \frac{n(n-1)}2  - \frac{n}2 \right) + \frac{n}2 = n(n-1.5)$$
linear transforms, at least when $n$ is even.  My intuition is that you probably can’t do better than that, although it is unclear how one might prove such a statement.
