16
$\begingroup$

It seems to me that any linear transformation in $R^{n\times m}$ is just a series of applications of rotation(actually i think any rotation can be achieved by applying two reflections, but not sure), reflection, shear, scaling and projection transformations. One or more of each kind in some order.

This is how I have been imagining it to myself, but I was unable to find proof of this on the internet.

Is this true? And if this is true, is there a way to find such a decomposition?

EDIT: to make it clear, I am asking whether it is true that $\forall A\in R^{n \times m} $,$$A=\prod_{i=1}^{k}P_i$$ Where $P_i$ is rotation, reflection, shear, scaling, or projection matrix in $R^{n_i\times m_i}$. Also $n,m,k\in N$,and $n_i,m_i\in N$ for all i.

And if it is true then how can we decompose it into that product.

  • 0
    The generality in which "linear transformation" makes sense is not the generality in which the other terms you're using make sense.2012-02-14
  • 0
    @QiaochuYuan Can you elaborate?2012-02-14
  • 0
    "Linear transformation" makes sense for vector spaces over any field, as does "shear" and "scaling." However, to define a notion of "rotation" requires an inner product (so we should ideally be working over $\mathbb{R}$ or $\mathbb{C}$), and depending on what you want out of "projection" or "reflection" those notions may also require an inner product.2012-02-14
  • 0
    @QiaochuYuan Sorry, I had in mind matrices of real numbers when I asked this question. I modified my question to reflect that.2012-02-14
  • 0
    http://math.stackexchange.com/questions/13150/extracting-rotation-scale-values-from-2d-transformation-matrix ?2012-02-14
  • 0
    Similar decomposition applies to [Mobius Transformations](http://en.wikipedia.org/wiki/Mobius_transformation#Decomposition_and_elementary_properties)2013-01-18
  • 0
    @QiaochuYuan, what is shear and scaling in finite fields for example, or non-zero characteristic? My understanding is that most generally projections are idempotents, and reflections are involutions (but perhaps don't exist in certain classes of fields).2013-01-18
  • 0
    @alan: a shear in two dimensions is a Jordan block with eigenvalue $1$ and scaling is just multiplication by a scalar (multiple of the identity matrix).2013-01-19

3 Answers 3

24

The question is not posed completely clearly, but I think that something close to what the questioner wants should follow quickly from the singular value decomposition, which states that any real matrix $A$ can be written in the form $$ A=UDV, $$ where $U$ and $V$ are square real orthogonal matrices and $D$ is a (possibly rectangular) diagonal matrix with nonnegative entries on the diagonal. Since $U$ and $V$ are orthogonal they are products of rotations and reflections, while $D$ can be thought of as a product of projections and scalings.

For example, if $$ A=\left(\begin{array}{cc}1&2x\\0&1\end{array}\right), $$ then $$ A= \left(\begin{array}{cc}\cos \phi&-\sin\phi\\\sin\phi&\cos\phi\end{array}\right) \left(\begin{array}{cc}\sqrt{x^2+1}-x&0\\0&\sqrt{x^2+1}+x\end{array}\right) \left(\begin{array}{cc}\cos\theta&-\sin\theta\\\sin\theta&\cos\theta\end{array}\right), $$ where $$ \phi=-\frac{\pi}{4}-\frac{1}{2}\arctan x, \qquad \theta=\frac{\pi}{4}-\frac{1}{2}\arctan x. $$

In reply to the comments below: Interpreting a diagonal matrix with positive entries along the diagonal as a scaling relies on allowing the scaling to be non-uniform, i.e., allowing it to scale different axes by different amounts. If the scaling matrices are restricted to be uniform, then, by using examples like the one above, you can write a square diagonal matrix with positive entries as a product of orthogonal matrices, shears, and a uniform scaling.

  • 0
    So it means that shear is also a product of reflections, projections and scaling? Can that be true?2013-01-18
  • 0
    I added an example of the SVD of a shear above.2013-01-18
  • 0
    How can a diagonal matrix be thought of as a product of projections and scalings? [Also, the middle matrix in your decomposition of the shear isn't diagonal.]2013-01-18
  • 0
    I made a typographical error; thank you for spotting that. A diagonal matrix with nonnegative entries projects onto the set of axes given by its non-zero entries, and then scales these axes. The scaling may be non-uniform as the diagonal matrix may use a different scale factor for each axis.2013-01-18
  • 0
    So are you saying that every positive semidefinite diagonalizable matrix is a scaling? I had assumed that "scaling" means a scalar multiple of the identity, and certainly no invertible diagonal matrix is a product of (orthogonal) projections and scalar multiples of $I$.2013-01-18
  • 2
    In some lines of work, it's common to call a diagonal matrix with positive entries a "scaling matrix", although, as you point out, it's not a scalar multiple of the identity.2013-01-18
4

The claim "any linear transformation is a series of applications projection transformations" is not correct. J. A. Erdos showed that every noninvertible $n\times n$ matrix is a finite product of projection matrices. An elmentary proof can be found here [An Elementary Proof That Every Singular Matrix Is a Product of Idempotent Matrices by J. Araújo and J. D. Mitchell, The American Mathematical Monthly, Vol. 112, No. 7 (Aug. - Sep., 2005), pp. 641-645] And it is not the case for invertible matrices generally.

  • 0
    If "any linear transformation is a series of applications projection transformations" is not true, I don't see how it says anything about "any linear transformation is a series of applications of projection, shear,reflection,rotation and scaling transformations". Now if it was true, then that is different matter :)2012-02-14
3

There are several things that are true and known for a long time, related to the question. First, we can consider non-singular matrices without much loss of generality, since any singular matrix can be written (in many ways) as non-singular composed with (orthogonal) projection.

As in another answer, the "singular value decomposition" (an example of a Cartan decomposition, valid in many other scenarios) expresses an arbitrary non-singular (real, for specificness) matrix as a product of rotation, diagonal matrix, and another rotation. Yes, this does express "shearing" as such a composition.

Another decomposition of non-singular real matrices is as a product of shear (upper triangular with 1's on the diagonal), diagonal, and then rotation. Among its other names, this is a special case of "Iwasawa decomposition".

Yet another is as product of upper triangular, permutation matrix (=exactly one non-zero entry, a "1", in each row and column), then another shear. This is a special case of "Bruhat decomposition".

Yes, each of these applies to the components of the others.