user
Every symmetric, positive definite matrix A can be decomposed into a product of a unique lower triangular matrix L and its transpose:

:   A
    =
    L

    L

    T
    {\displaystyle {\displaystyle A=LL^{T}}}

L
{\displaystyle {\displaystyle L}}
 is called the *Cholesky factor* of 

A
{\displaystyle {\displaystyle A}}
, and can be interpreted as a generalized square root of 

A
{\displaystyle {\displaystyle A}}
, as described in Cholesky decomposition.

In a 3x3 example, we have to solve the following system of equations:

:   A


    =


    (

    a

    11


    a

    21


    a

    31

    a

    21


    a

    22


    a

    32

    a

    31


    a

    32


    a

    33
    )

    =


    (

    l

    11

    0

    0

    l

    21


    l

    22

    0

    l

    31


    l

    32


    l

    33
    )


    (

    l

    11


    l

    21


    l

    31


    0


    l

    22


    l

    32


    0

    0


    l

    33
    )
    ≡
    L

    L

    T

    =


    (

    l

    11

    2


    l

    21

    l

    11


    l

    31

    l

    11

    l

    21

    l

    11


    l

    21

    2
    +

    l

    22

    2


    l

    31

    l

    21
    +

    l

    32

    l

    22

    l

    31

    l

    11


    l

    31

    l

    21
    +

    l

    32

    l

    22


    l

    31

    2
    +

    l

    32

    2
    +

    l

    33

    2
    )
    {\displaystyle {\displaystyle {\begin{aligned}A&={\begin{pmatrix}a\_{11}&a\_{21}&a\_{31}\\a\_{21}&a\_{22}&a\_{32}\\a\_{31}&a\_{32}&a\_{33}\\\end{pmatrix}}\\&={\begin{pmatrix}l\_{11}&0&0\\l\_{21}&l\_{22}&0\\l\_{31}&l\_{32}&l\_{33}\\\end{pmatrix}}{\begin{pmatrix}l\_{11}&l\_{21}&l\_{31}\\0&l\_{22}&l\_{32}\\0&0&l\_{33}\end{pmatrix}}\equiv LL^{T}\\&={\begin{pmatrix}l\_{11}^{2}&l\_{21}l\_{11}&l\_{31}l\_{11}\\l\_{21}l\_{11}&l\_{21}^{2}+l\_{22}^{2}&l\_{31}l\_{21}+l\_{32}l\_{22}\\l\_{31}l\_{11}&l\_{31}l\_{21}+l\_{32}l\_{22}&l\_{31}^{2}+l\_{32}^{2}+l\_{33}^{2}\end{pmatrix}}\end{aligned}}}}

We can see that for the diagonal elements (

l

k
k
{\displaystyle {\displaystyle l\_{kk}}}
) of 

L
{\displaystyle {\displaystyle L}}
 there is a calculation pattern:

:   l

    11
    =

    a

    11
    {\displaystyle {\displaystyle l\_{11}={\sqrt {a\_{11}}}}}
:   l

    22
    =

    a

    22
    −

    l

    21

    2
    {\displaystyle {\displaystyle l\_{22}={\sqrt {a\_{22}-l\_{21}^{2}}}}}
:   l

    33
    =

    a

    33
    −
    (

    l

    31

    2
    +

    l

    32

    2
    )
    {\displaystyle {\displaystyle l\_{33}={\sqrt {a\_{33}-(l\_{31}^{2}+l\_{32}^{2})}}}}

or in general:

:   l

    k
    k
    =

    a

    k
    k
    −

    ∑

    j
    =
    1

    k
    −
    1

    l

    k
    j

    2
    {\displaystyle {\displaystyle l\_{kk}={\sqrt {a\_{kk}-\sum \_{j=1}^{k-1}l\_{kj}^{2}}}}}

For the elements below the diagonal (

l

i
k
{\displaystyle {\displaystyle l\_{ik}}}
, where 

i
>
k
{\displaystyle {\displaystyle i>k}}
) there is also a calculation pattern:

:   l

    21
    =


    1

    l

    11

    a

    21
    {\displaystyle {\displaystyle l\_{21}={\frac {1}{l\_{11}}}a\_{21}}}
:   l

    31
    =


    1

    l

    11

    a

    31
    {\displaystyle {\displaystyle l\_{31}={\frac {1}{l\_{11}}}a\_{31}}}
:   l

    32
    =


    1

    l

    22
    (

    a

    32
    −

    l

    31

    l

    21
    )
    {\displaystyle {\displaystyle l\_{32}={\frac {1}{l\_{22}}}(a\_{32}-l\_{31}l\_{21})}}

which can also be expressed in a general formula:

:   l

    i
    k
    =


    1

    l

    k
    k

    (


    a

    i
    k
    −

    ∑

    j
    =
    1

    k
    −
    1

    l

    i
    j

    l

    k
    j
    )
    {\displaystyle {\displaystyle l\_{ik}={\frac {1}{l\_{kk}}}\left(a\_{ik}-\sum \_{j=1}^{k-1}l\_{ij}l\_{kj}\right)}}

**Task description**

The task is to implement a routine which will return a lower Cholesky factor 

L
{\displaystyle {\displaystyle L}}
 for every given symmetric, positive definite nxn matrix 

A
{\displaystyle {\displaystyle A}}
. You should then test it on the following two examples and include your output.

Example 1:

```
25  15  -5                 5   0   0
15  18   0         -->     3   3   0
-5   0  11                -1   1   3

```

Example 2:

```
18  22   54   42           4.24264    0.00000    0.00000    0.00000
22  70   86   62   -->     5.18545    6.56591    0.00000    0.00000
54  86  174  134          12.72792    3.04604    1.64974    0.00000
42  62  134  106           9.89949    1.62455    1.84971    1.39262

```

Note

1. The Cholesky decomposition of a Pascal upper-triangle matrix is the Identity matrix of the same size.
2. The Cholesky decomposition of a Pascal symmetric matrix is the Pascal lower-triangle matrix of the same size.
assistant
(formerly Perl 6)

```
sub cholesky(@A) {
    my @L = @A »×» 0;
    for ^@A -> \i {
        for 0..i -> \j {
            @L[i;j] = (i == j ?? &sqrt !! 1/@L[j;j] × * )\      # select function
                      (@A[i;j] - [+] (@L[i;*] Z× @L[j;*])[^j])  # provide value
        }
    }
    @L
}

.fmt('%3d').say for cholesky [
    [25],
    [15, 18],
    [-5,  0, 11],
];

say '';

.fmt('%6.3f').say for cholesky [
    [18, 22,  54,  42],       
    [22, 70,  86,  62],
    [54, 86, 174, 134],       
    [42, 62, 134, 106],
];

```

Output:

```
  5
  3   3
 -1   1   3

 4.243  0.000  0.000  0.000
 5.185  6.566  0.000  0.000
12.728  3.046  1.650  0.000
 9.899  1.625  1.850  1.393
```