Welcome to the Cholesky decomposition calculator. In this accompanying text to the tool, we'll learn all there is to know about the Cholesky factorization, which decomposes a matrix into a product of matrices. We'll specifically cover how to calculate the Cholesky decomposition and an example of Cholesky decomposition for a 3×3 matrix.

What is a matrix decomposition?

Before we can learn about the Cholesky decomposition, we must define what a matrix decomposition is. In the world of linear algebra, a matrix decomposition (or a matrix factorization) is the factorization of a matrix into a product of matrices. So, just as you can factorize 1616 into groups of products like 4×44\times4 or 2×82\times8, you can factorize a matrix like AA below… but how?

A=[2335]A = \begin{bmatrix} 2 & 3 \\ 3 & 5 \\ \end{bmatrix}

Factorizing a matrix is much harder than a number. Lucky for us, mathematicians have discovered many different methods of performing matrix decompositions. The most famous of these methods are the LU decomposition, the QR decomposition, and the Cholesky decomposition. Which method you'd want to use depends on the problem you're trying to solve.

What is the Cholesky decomposition?

Knowing what matrix decomposition is, we can go on to define the Cholesky decomposition. The Cholesky decomposition (or the Cholesky factorization) is the factorization of a matrix AA into the product of a lower triangular matrix LL and its transpose. We can rewrite this decomposition in mathematical notation as:

A=LLTA = L\cdot L^T

To be Cholesky-decomposed, matrix AA needs to adhere to some criteria:

  • AA must be symmetric, i.e. AT=AA^T = A.

  • By extension, this means AA must be square.

  • AA must be positive definite (meaning its eigenvalues must all be positive).

If AA doesn't tick all the items on our list, no suitable LL can exist.

How to calculate the Cholesky decomposition?

The goal of any matrix decomposition method is to find the factorization's terms, and so we want to find the lower triangular matrix LL. The Cholesky decomposition has no single mathematical formula, but it is easily obtained by hand for a small matrix. For larger matrices, there's an algorithmic process to follow.

Let's begin by looking at the simple 2×22\times2 matrix case symbolically. We first define:

A=[a1,1a1,2a2,1a2,2]A = \begin{bmatrix} a_{1,1} & a_{1,2} \\ a_{2,1} & a_{2,2} \\ \end{bmatrix}

…and:

L=[b1,10b2,1b2,2]L = \begin{bmatrix} b_{1,1} & 0 \\ b_{2,1} & b_{2,2} \\ \end{bmatrix}

Note that the elements of LL above its diagonal are zero, as LL is a lower triangular matrix.

We know from the definition of the Cholesky factorization that A=LLTA = L\cdot L^T, so let's take a look at the right-hand side of this equation.

 LLT= [b1,10b2,1b2,2][b1,1b2,10b2,2]= [(b1,1)2b1,1b2,1b1,1b2,1(b2,1)2+(b2,2)2]\begin{split} &\ L\cdot L^T \\ =&\ \begin{bmatrix} b_{1,1} & 0 \\ b_{2,1} & b_{2,2} \\ \end{bmatrix} \cdot \begin{bmatrix} b_{1,1} & b_{2,1} \\ 0 & b_{2,2} \\ \end{bmatrix} \\ =&\ \begin{bmatrix} (b_{1,1})^2 & b_{1,1}\cdot b_{2,1} \\ b_{1,1}\cdot b_{2,1} & (b_{2,1})^2 + (b_{2,2})^2 \\ \end{bmatrix} \end{split}

Knowing the above and that A=LLTA = L\cdot L^T, we can just equate corresponding elements of AA and LLTL\cdot L^T and solve the equations:

a1,1=(b1,1)2 b1,1=a1,1a2,1=b1,1b2,1 b2,1=a2,1 / b1,1a2,2=(b2,1)2+(b2,2)2 b2,2=a2,2(b2,1)2\begin{alignat*}{2} & a_{1,1} = (b_{1,1})^2 \\ \therefore\ & b_{1,1} = \sqrt{a_{1,1}} \\ & a_{2,1} = b_{1,1}\cdot b_{2,1} \\ \therefore\ & b_{2,1} = a_{2,1}\ /\ b_{1,1} \\ & a_{2,2} = (b_{2,1})^2 + (b_{2,2})^2 \\ \therefore\ & b_{2,2} = \sqrt{a_{2,2} - (b_{2,1})^2} \end{alignat*}

Notice that we need earlier elements of LL to solve for the later elements: b2,2b_{2,2} needs b2,1b_{2,1}, which needs b1,1b_{1,1}.

We can use the equations above to solve LL for the 3×33\times3 matrix AA that we defined at the top:

A=[2335]L=[203212]\begin{split} A &= \begin{bmatrix} 2 & 3 \\ 3 & 5 \end{bmatrix} \\ \therefore L &= \begin{bmatrix} \sqrt{2} & 0 \\ \frac{3}{\sqrt{2}} & \sqrt{\frac{1}{2}}\end{bmatrix} \end{split}

The principles of the above example apply to the Cholesky factorization of any sized matrix. For larger matrices, we can generalize the process with the following two equations.

For elements on LL's diagonal:

bj,j=aj,jk=1j1(bj,k)2b_{j,j} = \sqrt{a_{j,j} - \sum_{k=1}^{j-1} (b_{j,k})^2}

For elements off LL's diagonal:

bi,j=1bj,j(aj,jk=1j1bi,kbj,k)(i>j)b_{i,j} = \frac{1}{b_{j,j}}\left(a_{j,j} - \sum_{k=1}^{j-1} b_{i,k}\cdot b_{j,k}\right)\quad (i > j)

How to use the Cholesky decomposition calculator?

With the help of our calculator, you can easily calculate LL if you know what AA is. Remember, AA must be symmetric and positive definite. If it's not, the calculator can't give you LL as no LL that complies with A=LLTA = L\cdot L^T exists.

  1. Select AA's shape. Our Cholesky decomposition solver supports 2×22\times2, 3×33\times3, and 4×44\times4 matrices.

  2. Give the calculator your matrix AA. The matrix's elements are separated by row — see the graphical representation at the top of the calculator if you're unsure.

  3. Find the result LL below. Our Cholesky decomposition solver will calculate LL and display it below your matrix. If AA is not symmetric and positive definite, the calculator will notify you accordingly.

Example Cholesky decomposition of a 3×3 matrix

Now that we know how to compute the Cholesky factorization for a matrix of any size, let's do an example. We'll use the general-case algorithmic equations we've just discussed to solve LL given the following 3×33\times3 matrix AA:

A=[2515515131151121]A = \begin{bmatrix} 25 & 15 & 5 \\ 15 & 13 & 11 \\ 5 & 11 & 21 \\ \end{bmatrix}

We can jump straight into the solving process, starting at the top left and moving left-to-right, top-to-bottom.

b1,1=a1,1=5b2,1=a2,1 / b1,1=3b2,2=a2,2(b2,1)2=2b3,1=a3,1 / b1,1=1b3,2=(a3,2b3,1b2,1) / b2,2=4b3,3=a3,3(b3,1)2(b3,2)2=2\begin{alignat*}{2} b_{1,1} &= \sqrt{a_{1,1}} &= 5 \\ b_{2,1} &= a_{2,1}\ /\ b_{1,1} &= 3 \\ b_{2,2} &= \sqrt{a_{2,2} - (b_{2,1})^2} &= 2 \\ b_{3,1} &= a_{3,1}\ /\ b_{1,1} &= 1 \\ b_{3,2} &= (a_{3,2} - b_{3,1}\cdot b_{2,1})\ /\ b_{2,2} &= 4 \\ b_{3,3} &= \sqrt{a_{3,3} - (b_{3,1})^2 - (b_{3,2})^2} &= 2 \\ \end{alignat*}

And so, after all our effort, we've fully obtained LL,

L=[500320142]L = \begin{bmatrix} 5 & 0 & 0 \\ 3 & 2 & 0 \\ 1 & 4 & 2 \\ \end{bmatrix}

Finally, to test our answer, we can see if LLTL\cdot L^T really is equal to AA:

 LLT= [500320142][531024002]= [525×35×13×532+223×1+2×41×51×3+4×212+42+22]= [2515515131151121]= A\begin{split} &\ L\cdot L^T \\ =&\ \begin{bmatrix} 5 & 0 & 0 \\ 3 & 2 & 0 \\ 1 & 4 & 2 \end{bmatrix} \cdot \begin{bmatrix} 5 & 3 & 1 \\ 0 & 2 & 4 \\ 0 & 0 & 2 \end{bmatrix} \\ =&\ \begin{bmatrix} 5^2 & 5\times3 & 5\times1 \\ 3\times5 & 3^2 + 2^2 & 3\times1 + 2\times4 \\ 1\times5 & 1\times3 + 4\times2 & 1^2 + 4^2 + 2^2 \\ \end{bmatrix} \\ =&\ \begin{bmatrix} 25 & 15 & 5 \\ 15 & 13 & 11 \\ 5 & 11 & 21 \end{bmatrix} \\ =&\ A \end{split}

Perfect! We've just performed a complete decomposition of AA. You can also try out this example in our Cholesky decomposition calculator.

What are the applications of the Cholesky decomposition?

Matrix decomposition methods exploit the structure of the factorization's terms to make solving system of equations easier. Remember how we said that LL is lower triangular? Lower triangular matrices are especially easy to work with, and therefore the Cholesky decomposition is frequently the method of choice in solving systems of equations.

FAQ

How do you determine whether a matrix has a Cholesky decomposition?

For the matrix A to have a Cholesky decomposition, it must be symmetric, and it must be positive definite (meaning it must have only positive eigenvalues). If A does not adhere to these requirements, it cannot have a Cholesky decomposition, meaning no matrix L that satisfies L·LT = A can exist.

What does the Cholesky decomposition do?

Like any matrix decomposition method, the Cholesky decomposition takes a matrix A and factorizes it. It produces a lower triangular matrix L, which when multiplied with its transpose LT produces the original matrix A. This is valuable in many matrix operations, as the structure of a lower triangular matrix can be exploited to make the operations compute much faster.

What is a symmetric matrix?

A symmetric matrix is one that is equal to its transpose. Redefined mathematically, symmetric matrices satisfy the condition A = AT. This has the implication that the matrix must also be square. Graphically, a symmetric matrix is symmetric along its main diagonal.

What is a positive definite matrix?

A positive definite matrix is a matrix with only positive eigenvalues. The formal mathematical definition is that matrix A is positive definite if zT·A·z > 0 for every nonzero column vector z. Alternatively, A is only positive definite if it has a Cholesky decomposition.

What is the Cholesky decomposition of the identity matrix?

The identity matrix's Cholesky decomposition is also the identity matrix. This is because the identity matrix's transpose is itself (IT = I) and so I·IT = I·I = I. In general, the Cholesky decomposition L of a diagonal matrix D is also diagonal, and its diagonal entries are the square roots of D's. When the diagonal entries are all 1 like they are in I, we get the identity matrix back.

Rijk de Wet
A=
a₁a₂
b₁b₂
Matrix size
2x2
First row
a₁
a₂
Second row
b₁
b₂
People also viewed…

Grams to cups

The grams to cups calculator converts between cups and grams. You can choose between 20 different popular kitchen ingredients or directly type in the product density.

Perimeter of a polygon

How to find the perimeter of a polygon? What is the perimeter of a polygon formula? This perimeter of a polygon calculator knows the answer!
main background