6
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ I found this question in my favourites and I'm also curious about the answer, so I've started a bounty. $\endgroup$
    – user856
    Commented Apr 22, 2019 at 17:47

1 Answer 1

3
+25
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ A proof could look like a specific 3x3 matrix which is shown not to be expressible by any product of 3 2x2 matrices. One could even try to brute force a counter example by going into the booleans. There are 512 3x3 matrices in Z/2Z and less then 110592 ways of composing 3 2x2. $\endgroup$
    – Arthur B.
    Commented Apr 26, 2019 at 13:47
  • 2
    $\begingroup$ (tried them, all 512 can be re-created) $\endgroup$
    – Arthur B.
    Commented Apr 26, 2019 at 14:00
  • $\begingroup$ @ArthurB. - Sharp idea and a take I would never have thought of. But while it disproves the original conjecture for a specific n, it doesn't necessarily disprove it for all n, nor provides a limit of what is possible. $\endgroup$ Commented Apr 26, 2019 at 15:03
  • $\begingroup$ Of course, but I think it's probably false that you can recreate an arbitrary n x n with a product of n x (n - 1)/2 2x2 transforms. So by increasing n and p we might hit a counterexample. $\endgroup$
    – Arthur B.
    Commented Apr 27, 2019 at 18:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .