Decomposition of Matrix

Decomposition is a method of splitting a matrix into multiplication of multiple matrix in the following form. Each factor is simpler than M, for example triangular, orthogonal or diagonal. So one hard problem about M turns into a short sequence of easy problems about its factors.

M = AB..N

, where M is original matrix. A,B,...,N are broken down matrix components

Think of it like breaking apart a big puzzle into smaller pieces that are easier to work with. These smaller matrices can then be used to solve problems, analyze data, or make calculations more efficient.

In short, matrix decomposition is a technique used in linear algebra to break a matrix into smaller, more manageable matrices. This helps to simplify complex problems and can make calculations more efficient.

How many matrix you split into and the characteristics of splitted matrix varies depending on each specific decomposition method.

Actually 'breaking one thing into multiple other things' is one of the most common techniques in mathematics. For example, we often break a number into multiples of other numbers as follows.

30 = 2 x 3 x 5

We also break a polynomial into the multiples of other polynomials as shown below.

x⁴ - 5 x³ - 7 x² + 29 x + 30 = (x+2)(x+1)(x-3)(x-5)

Why breaking it down ?

Question is "Why we do this kind of break down ?". Sometimes we may do this kind of thing just for mathematical fun or curiosity, but in most case (especially in engineering area) we do this because we can get some benefit from it. For example, if you are asked to plot a graph for x⁴ - 5 x³ - 7 x² + 29 x + 30, you may have to do a lot of work (a lot of punching keys on your pocket calculator), but if you break the polynomial into (x+2)(x+1)(x-3)(x-5), you would be able to overal shape of the graph without doing even single calculation. Same thing applies to Matrix decomposition. We decompose a Matrix into multiple other matrices because there are advantages doing it. What kind of benefit you can get from the matrix decomposition ? We can think of mainly two advantages

it helps getting solution for a matrix equation with very large number of elements
it helps you understand the characteristics of the original matrix (or original system equation that the matrix represents)

Then you may ask "Why I don't see this kind of benefit in the linear algebra course ?". "It just look like trying to make simple things more complex.", "It is seems to be designed just to give headache to students".

Mainly two reasons for this

Linear Algebra textbook or the course hardly mention the practical meaning and advanges of them. They just shows calculation process.
Most of textbook examples are very small sized matrix from a small set of system equations. In this case, the overhead of decomposing the matrix is greater than the benefit you can get from the process. So you wouldn't see any benefit from it and keep grumping "Why do I have to do this kind of meaningless stuffs".

However if you are given a matrix equation with a huge matrix (like 1000000 x 1000000), then you would start seeing the benefit of doing decomposition. Of course, you cannot decompose 1000000 x 1000000 by hand. You have to use computer. Then you may ask "If I use computer, why bother to decompose ? Computer would do the calculation directly from the original matrix". But in reality it is not. If the size of matrix is very large, there would be huge differences between with and without decomposition even for the high performance computer.

Let's put numbers on that claim with LU decomposition. Take a dense n x n system Ax = b with n = 10000. Gaussian elimination on A costs about 2n³/3, which is 6.7 x 10¹¹ floating point operations. If you keep the result as the two factors L and U, each new right-hand side b needs only two triangular solves. Those cost about 2n², which is 2 x 10⁸ operations. So every b after the first one is about 3300 times cheaper. Without the factors, the computer repeats the full elimination for every b.

The second advantage works in a similar way. An eigen decomposition shows the eigenvalues, and they tell you whether a system grows, decays or oscillates. An SVD shows the singular values. The ratio of the largest to the smallest singular value is the condition number, and it tells you how much the matrix amplifies errors in its input.

Factor once, solve many times : the expensive part of solving a linear system is the factorization. After it, each new right-hand side costs n² operations instead of n³.
The factors are easy matrices : a triangular matrix is solved by substitution, an orthogonal matrix is inverted by its transpose, and a diagonal matrix is inverted by taking reciprocals. Every decomposition on this page produces factors of these kinds.
Small textbook examples hide the gain : for a 3 x 3 matrix, the factorization costs about as much as solving the system directly. The saving grows in proportion to n, so it appears only for large matrices.
The factors also describe the matrix : eigenvalues, singular values and the rank can be read directly from the factors. The original matrix hides the same numbers.

Some Popular Examples of Matrix Decomposition

There are various types of matrix decompositions, such as LU decomposition, QR decomposition, and singular value decomposition (SVD). These different decompositions are like using different strategies to break apart the puzzle, and each has its own set of applications and benefits.

Which one should you use? The answer depends on the shape of the matrix and on the question you are asking. LU works on a square matrix and answers "solve Ax = b". QR works on any matrix with independent columns and is the standard tool for least squares. Eigen decomposition needs a square matrix with enough independent eigenvectors. SVD works on every matrix, square or not, and so it is the most general of the four. The table below compares them.

Decomposition	Form	Which matrices	Factors	Typical use
LU	A = LU, or PA = LU with row exchanges	square	L lower triangular with 1 on the diagonal, U upper triangular, P a permutation	solving Ax = b for many b, determinant
QR	A = QR	m x n with independent columns	Q with orthonormal columns, R upper triangular	least squares, eigenvalue algorithms
Eigen	A = V Λ V^-1	square, with n independent eigenvectors	V holds the eigenvectors, Λ is diagonal with the eigenvalues	powers of A, dynamic systems, stability
SVD	A = U S V^H	any m x n matrix	U and V unitary, S diagonal with the singular values σ₁ >= σ₂ >= ... >= 0	rank, condition number, PCA, low rank approximation, MIMO channels

To see the difference, let's decompose one small matrix in all four ways. The numbers below were computed with numpy, and each product was multiplied back to check that it gives A. The signs of the vectors in Q, V and U are a convention. Matlab or another library may flip the sign of a whole column, and the result is still correct.

A = [ 4  3 ; 6  3 ]           det(A) = -6

LU      L = [ 1    0 ; 1.5  1 ]                   U = [ 4  3 ; 0  -1.5 ]
QR      Q = [ 0.5547  0.8321 ; 0.8321 -0.5547 ]   R = [ 7.2111  4.1603 ; 0  0.8321 ]
Eigen   λ₁ = 7.7720,  λ₂ = -0.7720
        v₁ = [ 0.6225 ; 0.7826 ],   v₂ = [ -0.5322 ; 0.8466 ]
SVD     σ₁ = 8.3356,  σ₂ = 0.7198
        U = [ 0.5958  0.8031 ; 0.8031 -0.5958 ]   V = [ 0.8640 -0.5035 ; 0.5035  0.8640 ]

Each factorization shows a different property of the same matrix. The diagonal of U in the LU result multiplies to 4 x -1.5 = -6, which is the determinant. The eigenvalues also multiply to -6, and they add to 7, which is the trace. The singular values are always positive, and they multiply to |det(A)| = 6. Their ratio, 8.3356 / 0.7198 = 11.6, is the condition number of A.

See http://en.wikipedia.org/wiki/Matrix_decomposition and see followings in sharetechnote in this page as a specific example. (I will keep adding more examples when I have chance)

SVD always exists : every real or complex matrix has an SVD, even a rectangular or singular one. The other three decompositions need extra conditions on the matrix.
Eigen and SVD agree only in a special case : for a symmetric positive semidefinite matrix, the eigenvalues and the singular values are the same numbers. For the matrix above they differ, because A is not symmetric.
Choose by the question : use LU to solve square systems, QR for least squares, eigen decomposition for repeated application of A, and SVD for rank and approximation.
Pivoting changes LU in practice : a library LU routine exchanges rows for numerical stability. For the matrix above, scipy returns PA = LU with the rows of A swapped, so its L and U differ from the hand result.