---
# Section 1.4: Positive Definite Systems; Cholesky Decomposition
---

After triangular linear systems, the next easiest type of linear system to solve is the **symmetric positive definite** linear system.

A matrix $A \in \mathbb{R}^{n \times n}$ is **symmetric** if $A = A^T$.

For example,

$$
A = 
\begin{bmatrix}
1 & 2 & 3 \\
2 & 4 & 5 \\
3 & 5 & 6
\end{bmatrix}
$$

is a symmetric matrix.

A matrix $A \in \mathbb{R}^{n \times n}$ is called **positive definite** if $A$ is symmetric and 

$$
x^T A x > 0, \qquad \text{for all nonzero $x \in \mathbb{R}^n$.}
$$

---

### Exercise:

Let $A = \begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix}$ and $x = \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \neq 0$. Prove that $x^T A x > 0$.


```julia
A = [ 2 -1; -1 2 ]
```


```julia
x = randn(2)
@show x
@show x'*A*x;
```

Let $x$ be a nonzero vector. Then,

\begin{eqnarray}
x^T A x
&=& 
\begin{bmatrix} x_1 \\ x_2 \end{bmatrix}^T
\begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix}
\begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \\
&=& 
\begin{bmatrix} x_1 \\ x_2 \end{bmatrix}^T
\begin{bmatrix} 2x_1 - x_2 \\ -x_1 + 2x_2 \end{bmatrix} \\
&=& x_1(2x_1 - x_2) + x_2(-x_1 + 2x_2) \\
&=& 2x_1^2 - 2 x_1 x_2 + 2x_2^2 \\
&=& x_1^2 + (x_1^2 - 2 x_1 x_2 + x_2^2) + x_2^2 \\
&=& x_1^2 + (x_1 - x_2)^2 + x_2^2 \\
&\ge& x_1^2 + x_2^2 \\
&>& 0,
\end{eqnarray}

since $x$ is a nonzero vector. Therefore, the symmetric matrix $A$ is positive definite.


```julia
x'*A*x
```


```julia
x[1]^2 + (x[1] - x[2])^2 + x[2]^2
```

---

## Properties of positive definite matrices

(1) If $A$ is positive definite, then $A$ is nonsingular.

(2) If $A$ is positive definite, then $Ax = b$ has a unique solution.

(3) If $A = M^TM$ for some nonsingular $M \in \mathbb{R}^{n \times n}$, then $A$ is positive definite.

(4) $A$ is positive definite $\Longleftrightarrow$ all eigenvalues of $A$ are positive.


```julia
using LinearAlgebra
```


```julia
eigvals(A)
```

---
### Exercise:

Prove property (1) and deduce property (2).

#### Proof:

Let $A$ be a symmetric positive definite matrix. Suppose, for the sake of contradiction, that $A$ is singular. Then there is a nonzero vector $x$ such that $Ax = 0$. So we have that $x^T A x = x^T 0 = 0$, which contradicts our assumption that $A$ is positive definite. Therefore, $A$ is nonsingular.

Since $A$ is nonsingular, any linear system $Ax = b$ has a unique solution. $\blacksquare$

---
### Exercise:

Based on property (3), write a `Julia` function `A = randspd(n)` that randomly generates an $n \times n$ symmetric positive definite matrix $A$. Check that the matrix $A$ is positive definite by using property (4).


```julia
function randspd(n)
    M = randn(n,n)
    A = M'M
end
```


```julia
A = randspd(5)
```


```julia
eigvals(A)
```


```julia
n = 5
M = randn(n,n)
eigvals(M)
```

---

## The Cholesky Decomposition

It turns out that every positive definite matrix $A$ can be written as $A = M^TM$, for some nonsingular matrix $M$.

> ### Cholesky Decomposition Theorem
> Let $A$ be positive definite.
> Then there is a **unique upper-triangular matrix** $R$ with **positive diagonal entries** such that
> $$A = R^T R.$$

We will see a proof of this theorem later.

---

### Exercise:

Computing the Cholesky factor of a random positive definite matrix $A$ using the `Julia` function `cholesky`. Check that the output is correct.


```julia
?cholesky
```


```julia
n = 5
A = randspd(n)
```


```julia
F = cholesky(A)
```


```julia
R = F.U
```


```julia
A - R'R
```

---

### Exercise:

The function `cholesky` will detect if $A$ is not positive definite. In fact, this is the **most efficient** method for testing if a symmetric matrix is positive definite or not.

See what happens when you give the `cholesky` function a matrix that is symmetric but not positive definite.


```julia
n = 5
M = randn(n,n)
A = M + M'
```


```julia
F = cholesky(A)
```


```julia
eigvals(A)
```


```julia
isposdef(A)
```


```julia
isposdef(randspd(n))
```

---

### Exercise:

Let $R$ be the Cholesky factor of a positive definite matrix $A$. 

1. Propose an algorithm for solving $Ax = b$ using the Cholesky factorization $A = R^TR$. Your algorithm should have **two** steps, a forward-substitution and a backward-substitution.

2. What is the flop count of your algorithm?

3. Implement your algorithm in `Julia`. Check that the output is correct.

#### Part 1

Suppose $A$ is symmetric positive definite and that $A = R^TR$ is its Cholesky decomposition. Suppose also that $Ax = b$. Then

$$
R^T R x = b.
$$

Let $z = R x$. Then $R^T z = b$ is a lower triangular linear system, and since the diagonal entries of $R$ are all positive, the matrix $R^T$ is nonsingular. So our algorithm is:

1. Solve $R^T z = b$ for the vector $z$ using forward substitution.
2. Solve $R x = z$ for the vector $x$ using backward substitution.

#### Part 2

Suppose that $A$ is $n \times n$. Then both $R$ and $R^T$ are $n \times n$. Then we have:

1. Solving $R^T z = b$ requires $n^2$ flops.
2. Solving $R x = z$ requires $n^2$ flops.

So, in total, solving $A x = b$ given the Cholesky decomposition of $A$ requires $2 n^2$ flops. Note this is the same flop count as multiplying a $n \times n$ matrix times a vector.

### Part 3


```julia
n = 5
A = randspd(n)
xtrue = randn(n)
b = A*xtrue

F = cholesky(A)
R = F.U

# Step 1 (forward substitution)
z = R'\b

# Step 2 (backward substitution)
x = R\z
```


```julia
x - xtrue
```

---
### Exercise:

Compute the Cholesky factor of $A$ by hand by writing $A = R^T R$ as follows.

$$ 
\begin{bmatrix}
 4 & -2 &  4 \\
-2 & 10 & -2 \\
 4 & -2 &  8 \\
\end{bmatrix} =
\begin{bmatrix}
r_{11} \\
r_{12} & r_{22} \\
r_{13} & r_{23} & r_{33} \\
\end{bmatrix}
\begin{bmatrix}
r_{11} & r_{12} & r_{13} \\
       & r_{22} & r_{23} \\
       &        & r_{33} \\
\end{bmatrix}
$$

Multiplying the two matrices on the rhs gives us

$$
\begin{bmatrix}
 4 & -2 &  4 \\
-2 & 10 & -2 \\
 4 & -2 &  8 \\
\end{bmatrix} =
\begin{bmatrix}
r_{11}^2 & r_{11} r_{12} & r_{11} r_{13} \\
r_{11} r_{12} & r_{12}^2 + r_{22}^2 & r_{12} r_{13} + r_{22} r_{23} \\
r_{11} r_{13} & r_{12} r_{13} + r_{22} r_{23} & r_{13}^2 + r_{23}^2 + r_{33}^2
\end{bmatrix}.
$$

Then we have:

1. $r_{11}^2 = 4 \implies r_{11} = 2$
2. $r_{11} r_{12} = -2 \implies 2 r_{12} = -2 \implies r_{12} = -1$
3. $r_{11} r_{13} = 4 \implies 2 r_{13} = 4 \implies r_{13} = 2$
4. $r_{12}^2 + r_{22}^2 = 10 \implies 1 + r_{22}^2 = 10 \implies r_{22} = 3$
5. $r_{12} r_{13} + r_{22} r_{23} = -2 \implies -2 + 3 r_{23} = -2 \implies r_{23} = 0$
6. $r_{13}^2 + r_{23}^2 + r_{33}^2 = 8 \implies 4 + 0 + r_{33}^2 = 8 \implies r_{33} = 2$

Therefore,

$$
R = \begin{bmatrix}
2 & -1 & 2 \\
  &  3 & 0 \\
  &    & 2
  \end{bmatrix}.
  $$


```julia
R = [ 2 -1 2; 0 3 0; 0 0 2]
```


```julia
R'R
```


```julia
A = [
    4 -2 4
    -2 10 -2
    4 -2 8 ]
```

---

### General Inner-Product Cholesky Formula

The general formulas for the entries $r_{ij}$ of the Cholesky factor $R$ of a positive definite matrix $A$ are given by

$$
\begin{align}
r_{ii} &= \sqrt{a_{ii} - \sum_{k=1}^{i-1} r_{ki}^2}, \\
r_{ij} &= \left(a_{ij} - \sum_{k=1}^{i-1} r_{ki} r_{kj}\right)\bigg/r_{ii}, \qquad j = i+1, \ldots, n. \\
\end{align}
$$

#### Example
$$
\begin{bmatrix}
 4 & -2 &  4 \\
-2 & 10 & -2 \\
 4 & -2 &  8 \\
\end{bmatrix} =
\begin{bmatrix}
r_{11}^2 & r_{11} r_{12} & r_{11} r_{13} \\
r_{11} r_{12} & r_{12}^2 + r_{22}^2 & r_{12} r_{13} + r_{22} r_{23} \\
r_{11} r_{13} & r_{12} r_{13} + r_{22} r_{23} & r_{13}^2 + r_{23}^2 + r_{33}^2
\end{bmatrix}.
$$


```julia
R = zeros(size(A))

# i = 1
R[1,1] = sqrt(A[1,1])
# j = 2
R[1,2] = (A[1,2])/R[1,1]
# j = 3
R[1,3] = (A[1,3])/R[1,1]

# i = 2
R[2,2] = sqrt(A[2,2] - R[1,2]^2)
# j = 3
R[2,3] = (A[2,3] - R[1,2]*R[1,3])/R[2,2]

# i = 3
R[3,3] = sqrt(A[3,3] - R[1,3]^2 - R[2,3]^2)

R
```


```julia
A - R'R
```

---

### Exercise:

Complete the following `Julia` function for the inner-product version of Cholesky's Algorithm.


```julia
function chol_ip(A::Symmetric)
        
    # Initialize R to be the upper-triangular part of A
    R = UpperTriangular(Matrix(A))

    n = size(A, 1)

    for i = 1:n
        # R[i,i] = sqrt(A[i,i] - sum_{k=1}^{i-1} R[k,i]^2)
        tmp = A[i,i] - sum([R[k,i]^2 for k=1:i-1])
        if tmp <= 0.0
            error("Matrix is not positive definite.")
        end
        R[i,i] = sqrt(tmp)
        
        for j = i+1:n
            # R[i,j] = (A[i,j] - sum_{k=1}^{i-1} R[k,i]*R[k,j]) / R[i,i]
            R[i,j] = (A[i,j] - sum([R[k,i]*R[k,j] for k=1:i-1]))/R[i,i]
        end
    end
    
    return R
end
```


```julia
A = Float64.(A)
```


```julia
A = Symmetric(A)
```


```julia
R = UpperTriangular(Matrix(A))
```


```julia
R = chol_ip(A)
```


```julia
B = copy(A)
```


```julia
B[1,1] = 3
```


```julia
chol_ip(B)
```


```julia
A = Symmetric(randn(3,3))
eigvals(A)
```


```julia
chol_ip(A)
```

---

### Exercise:

Develop the **Outer-Product Form of Cholesky's Algorithm** by partitioning $A = R^TR$ as:

$$
\begin{bmatrix}
a_{11} & b^T \\
b & \hat{A} \\
\end{bmatrix} = 
\begin{bmatrix}
r_{11} & 0 \\
s & \hat{R}^T \\
\end{bmatrix}
\begin{bmatrix}
r_{11} & s^T \\
0 & \hat{R} \\
\end{bmatrix}.
$$

1. Use block-matrix multiplication to multiply the matrices $R^T$ and $R$.
2. Based on the equations from part (1), derive a recursive algorithm for computing $R$.

\begin{eqnarray}
\begin{bmatrix}
a_{11} & b^T \\
b & \hat{A} \\
\end{bmatrix} &=& 
\begin{bmatrix}
r_{11}^2 & r_{11} s^T + 0 \hat{R} \\
s r_{11} + \hat{R}^T 0 & s s^T + \hat{R}^T \hat{R}
\end{bmatrix} \\
&=& 
\begin{bmatrix}
r_{11}^2 & r_{11} s^T  \\
r_{11} s & s s^T + \hat{R}^T \hat{R}
\end{bmatrix} \\
\end{eqnarray}

1. $r_{11}^2 = a_{11} \implies r_{11} = \sqrt{a_{11}}$
2. $r_{11} s^T = b^T \implies s^T = b^T/r_{11}$
3. $s s^T + \hat{R}^T \hat{R} = \hat{A} \implies \hat{R}^T \hat{R} = \hat{A} - s s^T$

---

### Exercise:

Complete the following `Julia` function for the recursive version of Cholesky's Algorithm.


```julia
function chol_rop(A)

    if !issymmetric(A)
        error("Matrix must be symmetric.")
    end
    n = size(A, 1)

    # Initialize R = 0 and the same size and datatype as A
    R = UpperTriangular(zeros(n, n))
    
    if A[1,1] <= 0.0
        error("Matrix is not positive definite")
    end
    
    R[1,1] = sqrt(A[1,1])
    if n > 1
        b = A[2:n,1]
        s = b/R[1,1]
        
        R[1,2:n] = s
                
        Â = A[2:n,2:n]
        R̂ = chol_rop(Â - s*s')
        
        R[2:n,2:n] = R̂
    end
    
    return R
end
```


```julia
n = 4
A = randspd(n)

R = chol_rop(A)
```


```julia
A - R'R
```


```julia
A = Symmetric(randn(n,n))
eigvals(A)
```


```julia
R = chol_rop(A)
```

---

### Exercise:

Develop the **Bordered Form of Cholesky's Algorithm** by partitioning $A = R^TR$ as:

$$
\begin{bmatrix}
\hat{A} & c \\
c^T & a_{nn} \\
\end{bmatrix} = 
\begin{bmatrix}
\hat{R}^T & 0 \\
h^T & r_{nn} \\
\end{bmatrix}
\begin{bmatrix}
\hat{R} & h \\
0 & r_{nn} \\
\end{bmatrix}
$$

1. Use block-matrix multiplication to multiply the matrices $R^T$ and $R$.
2. Based on the equations from part (1), derive a recursive algorithm for computing $R$.
3. Based on your recursive algorithm, determine the number of flops for computing the Cholesky decomposition of an $n \times n$ positive definite matrix $A$.

#### Part 1

$$
\begin{bmatrix}
\hat{A} & c \\
c^T & a_{nn} \\
\end{bmatrix} = 
\begin{bmatrix}
\hat{R}^T \hat{R} & \hat{R}^T h \\
h^T \hat{R} & h^T h + r_{nn}^2
\end{bmatrix}
$$

#### Part 2

1. $\hat{R}^T \hat{R} = \hat{A}$ (recursive call)
2. Solve $\hat{R}^T h = c$ for $h$ (forward substitution)
3. $h^T h + r_{nn}^2 = a_{nn} \implies r_{nn} = \sqrt{a_{nn} - h^T h}$

#### Part 3

Let $T_n$ be the number of flops to compute the Cholesky factor of an $n \times n$ symmetric positive definite matrix.

1. Requires $T_{n-1}$ flops.
2. Requires $(n-1)^2$ flops.
3. Computing $a_{nn} - h^T h$ requires $2(n-1)$ flops. Plus one more flop for the square root.

Therefore,

$$T_{n} = T_{n-1} + (n-1)^2 + 2(n-1) + 1$$

and $T_1 = 1$ (or $T_0 = 0$).

First note that

$$T_{n} = T_{n-1} + n^2 - 2n + 1 + 2n - 2 + 1.$$

Thus,

$$T_{n} = T_{n-1} + n^2.$$



Then

\begin{align}
T_{n} 
&= T_{n-1} + n^2 \\
&= T_{n-2} + (n-1)^2 + n^2 \\
&= T_{n-3} + (n-2)^2 + (n-1)^2 + n^2 \\
&\vdots \\
&= T_0 + (1)^2 + \cdots + (n-2)^2 + (n-1)^2 + n^2 \\
&= 1 + 2^2 + \cdots + (n-1)^2 + n^2 \\
&= \sum_{k=1}^n k^2 \\
&= \frac{n(n+1)(2n+1)}{6} \\
&= \frac{1}{3} n^3 + O(n^2).
\end{align}

---

## Proof of the Cholesky Decomposition Theorem

> ### Cholesky Decomposition Theorem
> Let $n$ be a positive integer. If $A$ is an $n \times n$ positive definite matrix, then there is a **unique $n \times n$ upper-triangular matrix** $R$ with **positive diagonal entries** such that
>
> $$A = R^T R.$$

We will prove this theorem using mathematical induction, based on the following partitioning.

$$
\begin{bmatrix}
\hat{A} & c \\
c^T & a_{nn} \\
\end{bmatrix} 
= 
\begin{bmatrix}
\hat{R}^T & 0 \\
h^T & r_{nn} \\
\end{bmatrix}
\begin{bmatrix}
\hat{R} & h \\
0 & r_{nn} \\
\end{bmatrix}
$$

First we need to prove the following lemma.

> ### Lemma
> Let $A$ be positive definite and partitioned as
>
> $$
A = 
\begin{bmatrix}
A_{11} & A_{12} \\
A_{21} & A_{22}
\end{bmatrix}
$$
>
>where $A_{11} \in \mathbb{R}^{n_1 \times n_1}$ and $A_{22} \in \mathbb{R}^{n_2 \times n_2}$. Then $A_{11}$ and $A_{22}$ are positive definite.

---
### Exercise:

Prove the lemma.

#### Proof.

Suppose, for the sake of contradiction, that $A_{11}$ is **not** positive definite. Then there is a nonzero vector $y \in \mathbb{R}^{n_1}$ such that $y^T A_{11} y \le 0$. Let

$$
x = \begin{bmatrix} y \\ 0 \end{bmatrix} \in \mathbb{R}^n.
$$

Since $y \ne 0$, we have that $x \ne 0$. Then,

$$
x^T A x = 
\begin{bmatrix} y \\ 0 \end{bmatrix}^T
\begin{bmatrix}
A_{11} & A_{12} \\
A_{21} & A_{22}
\end{bmatrix}
\begin{bmatrix} y \\ 0 \end{bmatrix} =
\begin{bmatrix} y \\ 0 \end{bmatrix}^T
\begin{bmatrix} A_{11} y \\ A_{21} y \end{bmatrix} =
y^T A_{11} y \le 0.
$$

Thus, $A$ is **not** positive definite. This contradicts our assumption that $A$ is positive definite. Therefore, it is not possible for $A_{11}$ to not be positive definite. So, $A_{11}$ is positive definite.

Similarly, $A_{22}$ can be shown to be positive definite as well. $\blacksquare$

---
### Exercise:

Use the following steps to prove the theorem.

1. Prove that the theorem is true for $n = 1$. This is the _base case_.

2. Suppose that the theorem is true for $n = k$. This is the _induction hypothesis_.

3. Let $n = k+1$ and let $A$ be an $n \times n$ positive definite matrix.

4. Show that there is a unique $n \times n$ upper-triangular matrix $R$ with positive diagonal entries such that $A = R^T R$ by considering the following partitioning of $A = R^T R$,

    $$
    \begin{bmatrix}
    \hat{A} & c \\
    c^T & a_{nn} \\
    \end{bmatrix} = 
    \begin{bmatrix}
    \hat{R}^T & 0 \\
    h^T & r_{nn} \\
    \end{bmatrix}
    \begin{bmatrix}
    \hat{R} & h \\
    0 & r_{nn} \\
    \end{bmatrix},
    $$
    
    and showing that there exist unique $\hat{R}$, $h$, and $r_{nn}$ that satisfy this equation.

### Proof.

#### Step 1: (base case)

Let $A = [a_{11}]$ be a $1 \times 1$ positive definite matrix. Let $x = [1]$, then $x^T A x = a_{11}$. Thus, $a_{11}$ must be a positive number.

Let $r_{11} = \sqrt{a_{11}}$, and let $R = [r_{11}]$. Then $R$ is an upper-triangular matrix with positive diagonal entries and $A = R^T R$.

Moreover, if $S = [s_{11}]$ with $s_{11} > 0$ and $A = S^T S$, then $a_{11} = s_{11}^2$. But then $s_{11} = \sqrt{a_{11}} = r_{11}$, so $S = R$.

#### Step 2: (induction hypothesis)

We now assume that if $A$ is $k \times k$ and symmetric positive definite, then there exists a unique upper-triangular matrix $R$ with positive diagonal entries such that $A = R^T R$.

#### Step 3: (start of induction step)

Let $n = k+1$ and let $A$ be a $n \times n$ symmetric positive definite matrix.

#### Step 4:

If $A = R^T R$, then we have

$$
\begin{bmatrix}
\hat{A} & c \\
c^T & a_{nn} \\
\end{bmatrix} = 
\begin{bmatrix}
\hat{R}^T & 0 \\
h^T & r_{nn} \\
\end{bmatrix}
\begin{bmatrix}
\hat{R} & h \\
0 & r_{nn} \\
\end{bmatrix}
$$

where $\hat{A}$ and $\hat{R}$ are $k \times k$ matrices, $c$ and $h$ are vectors of length $k$, and $a_{nn}$ and $r_{nn}$ are real numbers.

Then

$$
\begin{bmatrix}
\hat{A} & c \\
c^T & a_{nn} \\
\end{bmatrix} = 
\begin{bmatrix}
\hat{R}^T \hat{R} & \hat{R}^T h \\
h^T \hat{R} & h^T h + r_{nn}^2
\end{bmatrix}.
$$

This implies that

1. $\hat{A} = \hat{R}^T \hat{R}$,
2. $\hat{R}^T h = c$, and
3. $a_{nn} = h^T h + r_{nn}^2$.

Note that $\hat{A}$ is a $k \times k$ symmetric matrix and by the lemma $\hat{A}$ is also positive definite.

Therefore, by the induction hypothesis, there is a unique upper-triangular matrix $\hat{R}$ with positive diagonal entries such that $\hat{A} = \hat{R}^T \hat{R}$.

Since $\hat{R}$ is upper-triangular with positive diagonal entries, we know that it is nonsingular (i.e., invertible) since $\det(\hat{R})$ is the product of the diagonal entries of $\hat{R}$, so $\det(\hat{R}) \ne 0$.

Therefore, $\hat{R}^T h = c$ has a unique solution $h$ and 

$$h = \hat{R}^{-T} c.$$

Next, we need to have $r_{nn}^2 = a_{nn} - h^T h$ and $r_{nn} > 0$. That means that we need to show that

$$a_{nn} - h^T h > 0.$$

To do this, we will use the fact that $x^T A x > 0$ for all nonzero vectors $x$.

First note that

\begin{align}
a_{nn} - h^T h 
&= a_{nn} - \left(\hat{R}^{-T} c\right)^T \left(\hat{R}^{-T} c\right) \\
&= a_{nn} - c^T \hat{R}^{-1} \hat{R}^{-T} c \\
&= a_{nn} - c^T \left( \hat{R}^{T} \hat{R} \right)^{-1} c \\
&= a_{nn} - c^T \hat{A}^{-1} c. \\
\end{align}

We want to find a nonzero vector $x$ such that $x^T A x = a_{nn} - c^T \hat{A}^{-1} c$. To do this, we observe that

\begin{align}
x^T A x &=
\begin{bmatrix}
\hat{x} \\ x_n
\end{bmatrix}^T
\begin{bmatrix}
\hat{A} & c \\
c^T & a_{nn} \\
\end{bmatrix}
\begin{bmatrix}
\hat{x} \\ x_n
\end{bmatrix} \\
&=
\begin{bmatrix}
\hat{x} \\ x_n
\end{bmatrix}^T
\begin{bmatrix}
\hat{A}\hat{x} + c x_n \\
c^T \hat{x} + a_{nn} x_n \\
\end{bmatrix} \\
&=
\hat{x}^T \hat{A} \hat{x} + \hat{x}^T c x_n +
x_n c^T \hat{x} + a_{nn} x_n^2 \\
&=
\hat{x}^T \hat{A} \hat{x} + 2 x_n c^T \hat{x} + a_{nn} x_n^2.
\end{align}

Let $x_n = 1$. Then

$$
x^T A x = \hat{x}^T \hat{A} \hat{x} + 2 c^T \hat{x} + a_{nn}.
$$

Let $\hat{x} = -\hat{A}^{-1} c.$ Then

\begin{align}
x^T A x 
&= c^T \hat{A}^{-1} \hat{A} \hat{A}^{-1} c - 2 c^T \hat{A}^{-1} c + a_{nn} \\
&= c^T \hat{A}^{-1} I c - 2 c^T \hat{A}^{-1} c + a_{nn} \\
&= -c^T \hat{A}^{-1} c + a_{nn} \\
&= a_{nn} - c^T \hat{A}^{-1} c, \\
\end{align}

which is what we wanted.

Since $x_n = 1$, the vector $x$ is nonzero, so $x^T A x = a_{nn} - c^T \hat{A}^{-1} c = a_{nn} - h^T h > 0$.

Therefore, there is a unique positive $r_{nn}$ that satisfies $r_{nn}^2 = a_{nn} - h^T h$, and it is $r_{nn} = \sqrt{a_{nn} - h^T h}$.

Thus, $R$ is uniquely defined since $\hat{R}$, $h$, and $r_{nn}$ are all uniquely defined. $\blacksquare$

---

55a7f406487d88cee64c67105a4e3428e5dbff2d
ipynb
Jupyter Notebook
Section 1.4 - Positive Definite Systems; Cholesky Decomposition.ipynb
jesus-lua-8/fall2021math434
e6c6931676922193a6718b51c92232a3de7fa650
MIT
2021-08-31T21:01:22.000Z
2021-08-31T21:01:22.000Z
Section 1.4 - Positive Definite Systems; Cholesky Decomposition.ipynb
jesus-lua-8/fall2021math434
e6c6931676922193a6718b51c92232a3de7fa650
MIT
Section 1.4 - Positive Definite Systems; Cholesky Decomposition.ipynb
jesus-lua-8/fall2021math434
e6c6931676922193a6718b51c92232a3de7fa650
MIT
2021-11-16T19:28:56.000Z
2021-11-16T19:28:56.000Z
Qwen/Qwen-72B
1. YES
2. YES