3.7.3 Practice set: positive definiteness

Quadratic forms and positive definiteness

Quadratic forms and positive definiteness (lesson 3.7.1)

0 of 9 correct

1.
For $A = \begin{pmatrix} 1 & -2 \\ -2 & 5 \end{pmatrix}$ , find $\mathbf{x}^\top A\mathbf{x}$ at $\mathbf{x} = (3, 1)$
2.
Write $2x_1^2 - 6x_1x_2 + 7x_2^2$ as $\mathbf{x}^\top A\mathbf{x}$ with $A$ symmetric. What is $a_{12}$ ?
3.
$A = \begin{pmatrix} 5 & 2 \\ 2 & 2 \end{pmatrix}$ has trace 7 and determinant 6. What is the smallest value of $\mathbf{x}^\top A\mathbf{x}$ over unit vectors?
4.
Find the third leading minor, $\det A$ , of $\begin{pmatrix} 3 & 1 & 1 \\ 1 & 3 & 1 \\ 1 & 1 & 3 \end{pmatrix}$
5.
For which positive $k$ is $\begin{pmatrix} 4 & k \\ k & 1 \end{pmatrix}$ positive semidefinite but not positive definite?
6.
A positive definite matrix has eigenvalues 4 and 1. How far from the origin does the ellipse $q = 9$ cross the axis of the eigenvector with eigenvalue 4?
7.
For $M = \begin{pmatrix} 1 & 1 \\ 2 & 0 \end{pmatrix}$ and $\mathbf{x} = (1, 2)$ , find $\mathbf{x}^\top M^\top M\mathbf{x}$
8.
A symmetric $2 \times 2$ matrix has determinant 6 and trace $-5$ . How many of its eigenvalues are negative?
9.
$B = \begin{pmatrix} 2 & 6 \\ 0 & 2 \end{pmatrix}$ has eigenvalues 2 and 2. Find $\mathbf{x}^\top B\mathbf{x}$ at $\mathbf{x} = (1, -1)$

How to type answers

Powers with ^: x^7, 2^(1/3), a^-2.
Multiply with * or by writing side by side: 3x^2, 2(x+1).
ln(x) is the natural log, log(x, 2) is log base 2, e is Euler's number, sqrt(x) is a square root.
sin(x), cos(x) and tan(x) take radians; write pi for π and sin(x)^2 for sin²x.
Your first answer to each question is saved: it counts towards your score and brings the question back for review.
Exact answers like ln(20)/ln(3) are best. Decimals need about 4 significant figures.

The Cholesky factorisation

The Cholesky factorisation (lesson 3.7.2)

0 of 7 correct

1.
Find $l_{22}$ in the Cholesky factor of $\begin{pmatrix} 16 & 8 \\ 8 & 13 \end{pmatrix}$
2.
Find $l_{21}$ for the correlation matrix $\begin{pmatrix} 1 & -0.6 \\ -0.6 & 1 \end{pmatrix}$
3.
Find $l_{32}$ for $\begin{pmatrix} 9 & 3 & 6 \\ 3 & 5 & 0 \\ 6 & 0 & 9 \end{pmatrix}$
4.
For that matrix, $l_{33} = 2$ . Find $\det A$
5.
$\begin{pmatrix} 9 & 3 \\ 3 & c \end{pmatrix}$ is positive definite only when $c$ is above which number?
6.
With $L = \begin{pmatrix} 3 & 0 \\ 1 & 2 \end{pmatrix}$ , solve $LL^\top\mathbf{x} = (6, 6)$ . What is $x_1$ ?
7.
NumPy's Cholesky function reads only the lower triangle. For the non-symmetric $\begin{pmatrix} 4 & 1 \\ 3 & 5 \end{pmatrix}$ , what $l_{21}$ does it return?

How to type answers

Powers with ^: x^7, 2^(1/3), a^-2.
Multiply with * or by writing side by side: 3x^2, 2(x+1).
ln(x) is the natural log, log(x, 2) is log base 2, e is Euler's number, sqrt(x) is a square root.
sin(x), cos(x) and tan(x) take radians; write pi for π and sin(x)^2 for sin²x.
Your first answer to each question is saved: it counts towards your score and brings the question back for review.
Exact answers like ln(20)/ln(3) are best. Decimals need about 4 significant figures.

Coding exercise

Exercise

The Cholesky factorisation

Write cholesky(A) that returns the Cholesky factor $L$ of A as a NumPy array, by the column-by-column method of lesson 3.7.2. Do not call np.linalg.cholesky; the tests compare your answer with it.

Make a new decimal array first (np.array(A, dtype=float)), so the caller's matrix is left unchanged.
Raise ValueError if A is not square, or not symmetric (test with np.allclose(A, A.T)). NumPy itself skips this check.
For each column $j$ , compute $a_{jj} - \sum_{k<j} l_{jk}^2$ . If it is 0 or negative, raise ValueError: A is not positive definite. Otherwise $l_{jj}$ is its square root.
Then fill in the entries below the diagonal, $l_{ij} = (a_{ij} - \sum_{k<j} l_{ik}l_{jk}) / l_{jj}$ .

The tests use the examples of lesson 3.7.2, a correlation matrix and a random $6 \times 6$ matrix. They also try lesson 3.7.1's indefinite $N$ , its semidefinite $J$ , and $T$ , which fails only at the third step. Two more pass a matrix that is not symmetric and one that is not square.

See the tests

import numpy as np


def _expect_value_error(A, why):
    try:
        cholesky(A)
    except ValueError:
        return
    raise AssertionError(f"expected ValueError: {why}")


def test_two_by_two():
    """[[4, 2], [2, 5]] factors as L = [[2, 0], [1, 2]]"""
    expect_close(cholesky([[4, 2], [2, 5]]), np.array([[2.0, 0.0], [1.0, 2.0]]), what="cholesky([[4, 2], [2, 5]])")


def test_correlation():
    """A correlation of 0.6 gives L = [[1, 0], [0.6, 0.8]]"""
    expect_close(cholesky([[1, 0.6], [0.6, 1]]), np.array([[1.0, 0.0], [0.6, 0.8]]), what="cholesky of [[1, 0.6], [0.6, 1]]")


def test_three_by_three():
    """Lesson 3.7.2's 3 × 3 example gives L = [[2, 0, 0], [1, 3, 0], [-1, 1, 2]]"""
    A = [[4, 2, -2], [2, 10, 2], [-2, 2, 6]]
    expect_close(cholesky(A), np.array([[2.0, 0, 0], [1, 3, 0], [-1, 1, 2]]), what="cholesky of the 3 × 3 example")


def test_shape_of_L():
    """L is lower triangular with a positive diagonal, and L @ L.T gives A back"""
    A = np.array([[9.0, 3, 6], [3, 5, 0], [6, 0, 9]])
    L = np.asarray(cholesky(A), dtype=float)
    expect_equal(L.shape, (3, 3), what="the shape of L")
    expect_close(np.triu(L, 1), np.zeros((3, 3)), what="the entries above the diagonal of L")
    assert np.all(np.diag(L) > 0), f"the diagonal of L must be positive, got {np.diag(L)}"
    expect_close(L @ L.T, A, what="L @ L.T")


def test_matches_numpy():
    """A random positive definite 6 × 6 matrix matches np.linalg.cholesky"""
    rng = np.random.default_rng(37)
    M = rng.standard_normal((6, 6))
    A = M @ M.T + 6 * np.eye(6)
    expect_close(cholesky(A), np.linalg.cholesky(A), what="cholesky of the random 6 × 6 matrix")


def test_input_unchanged():
    """The caller's matrix is left unchanged, and whole-number input works"""
    A = np.array([[4, 2], [2, 5]])
    cholesky(A)
    expect_equal(A.tolist(), [[4, 2], [2, 5]], what="A after calling cholesky(A)")


def test_indefinite():
    """The indefinite [[1, 2], [2, 1]] is not positive definite: ValueError"""
    _expect_value_error([[1, 2], [2, 1]], "the last step needs the square root of 1 − 4 = −3")


def test_semidefinite():
    """The semidefinite [[1, 1], [1, 1]] is not positive definite: ValueError"""
    _expect_value_error([[1, 1], [1, 1]], "the last step needs the square root of 0, and l22 = 0 is not positive")


def test_fails_late():
    """Lesson 3.7.1's T passes two steps and fails at the third: ValueError"""
    _expect_value_error([[2, 1, 2], [1, 2, 1], [2, 1, 1]], "det T = −3, so the third step needs the square root of a negative number")


def test_not_symmetric():
    """[[4, 100], [2, 5]] is not symmetric: ValueError, where NumPy answers silently"""
    _expect_value_error([[4, 100], [2, 5]], "the matrix is not symmetric (np.linalg.cholesky reads only its lower triangle)")


def test_not_square():
    """A 2 × 3 matrix has no Cholesky factor: ValueError"""
    _expect_value_error([[1, 0, 0], [0, 1, 0]], "a 2 × 3 matrix is not square")

Quadratic forms and positive definiteness

The Cholesky factorisation

Coding exercise

Free further reading