03. Where do PSD matrices live?

Gram matrices give PSD matrices a geometric meaning. Optimization needs one more view: all $n\times n$ PSD matrices form a structured feasible region.

What shape do all Gram matrices make?

Take two PSD matrices from different vector configurations. Before calculating, predict whether every average between them will remain PSD. Then try to break the prediction by changing the mixing weight.

using LinearAlgebra

X = [1.0 0.7; 0.7 1.0]
Y = [2.0 -0.4; -0.4 0.5]

for θ in (0.0, 0.25, 0.5, 0.75, 1.0)
    Z = θ * X + (1 - θ) * Y
    println("θ=$θ  eigenvalues=", round.(eigvals(Symmetric(Z)); digits = 3))
end

θ=0.0  eigenvalues=[0.4, 2.1]
θ=0.25  eigenvalues=[0.611, 1.764]
θ=0.5  eigenvalues=[0.721, 1.529]
θ=0.75  eigenvalues=[0.598, 1.527]
θ=1.0  eigenvalues=[0.3, 1.7]

The experiment suggests that the segment joining two PSD matrices stays PSD. Now name and prove the larger pattern. Write

\[ \mathbb S_+^n=\{X\in\mathbb S^n:z^TXz\ge 0\text{ for every }z\in\mathbb R^n\}. \]

If $X,Y\succeq0$ and $a,b\ge0$, then

\[ z^T(aX+bY)z=a z^TXz+b z^TYz\ge0. \]

Thus $aX+bY$ is PSD. Closure under nonnegative scaling makes the set a cone; closure under addition and averaging makes it convex. Convexity explains the experiment and gives optimization algorithms a connected, continuous region to move through.

Go further: theory and geometry

Sections 1–3 of Vandenberghe and Boyd’s survey develop SDP formulations, spectrahedra, and duality in more depth: Semidefinite Programming. MIT OpenCourseWare also provides a concise semidefinite optimization lecture. These are optional theory references; the course does not depend on their notation or organization.

A negative mixing weight can leave the cone, which explains why the failed attempt to break the pattern must violate $a,b\ge0$. What happens when a valid mixture approaches the cone’s edge?

What happens at the edge?

A symmetric matrix is positive definite, written $X\succ0$, when every eigenvalue is strictly positive. These matrices form the interior of the PSD cone. A PSD matrix with at least one zero eigenvalue lies on the boundary.

for t in (0.0, 0.5, 0.9, 0.99, 1.0)
    M = [1.0 t; t 1.0]
    λ = eigvals(Symmetric(M))
    println((t = t, λmin = minimum(λ), determinant = det(M), rank = rank(M)))
end

(t = 0.0, λmin = 1.0, determinant = 1.0, rank = 2)
(t = 0.5, λmin = 0.5, determinant = 0.75, rank = 2)
(t = 0.9, λmin = 0.09999999999999992, determinant = 0.18999999999999995, rank = 2)
(t = 0.99, λmin = 0.009999999999999953, determinant = 0.01990000000000003, rank = 2)
(t = 1.0, λmin = 0.0, determinant = 0.0, rank = 1)

Rank therefore records geometry and location at once. If $X=VV^T$, then rank(X) is the dimension needed by the represented vectors. Low-rank PSD matrices live on the cone’s boundary. Later, exact cuts will correspond to the extreme case rank(X) == 1; the relaxation permits higher-dimensional geometry.

What happens when constraints slice the cone?

An SDP feasible set usually intersects the cone with affine equations. Such an intersection is called a spectrahedron. For example,

\[ \left\{X\succeq0:X_{11}=X_{22}=1\right\} = \left\{\begin{bmatrix}1&t\\t&1\end{bmatrix}:-1\le t\le1\right\}. \]

The interval is not an analogy; it is literally a one-dimensional affine slice of $\mathbb S_+^2$. Its endpoints are rank-one boundary matrices.

In three dimensions, fixing the diagonal to one gives the set of $3\times3$ correlation matrices. Pairwise entries cannot be chosen independently because the complete matrix must remain PSD. Chapter 04 optimizes over exactly that set.

How do we optimize over matrices?

In ordinary linear optimization, $c^Tx$ assigns a weight $c_i$ to each entry $x_i$ of a vector and adds the results. A matrix objective needs to do the same thing with entries $X_{ij}$.

For two matrices of the same size, define

\[ \langle C,X\rangle =\operatorname{tr}(C^TX) =\sum_{i,j}C_{ij}X_{ij}. \]

This is the trace inner product. Despite the name, the last expression shows the operation directly: multiply corresponding entries of $C$ and $X$, then add every product. The matrix $C$ contains the weights, and $X$ contains the quantities being chosen.

How can a matrix select one entry?

Suppose the decision matrix is symmetric:

\[ X= \begin{bmatrix} X_{11}&X_{12}\\ X_{12}&X_{22} \end{bmatrix}. \]

To extract its upper-left entry, use

\[ E_{11}= \begin{bmatrix} 1&0\\ 0&0 \end{bmatrix}, \qquad \langle E_{11},X\rangle=X_{11}. \]

Selecting an off-diagonal entry requires one extra detail. Both $X_{12}$ and $X_{21}$ appear in the entrywise sum, even though symmetry makes them equal. Put one half in each position:

\[ S_{12}= \begin{bmatrix} 0&\tfrac12\\ \tfrac12&0 \end{bmatrix}, \qquad \langle S_{12},X\rangle =\tfrac12X_{12}+\tfrac12X_{21} =X_{12}. \]

The halves prevent the same symmetric entry from being counted twice.

using LinearAlgebra

X_trial = [1.0 0.25; 0.25 1.0]
E11 = [1.0 0.0; 0.0 0.0]
E22 = [0.0 0.0; 0.0 1.0]
S12 = [0.0 0.5; 0.5 0.0]

@assert tr(S12' * X_trial) ≈ sum(S12 .* X_trial)

(selected_off_diagonal = sum(S12 .* X_trial),
 first_diagonal = sum(E11 .* X_trial),
 second_diagonal = sum(E22 .* X_trial))

(selected_off_diagonal = 0.25, first_diagonal = 1.0, second_diagonal = 1.0)

The same operation can score a whole matrix, not merely select one entry. Different nonzero entries of $C$ assign different weights to the corresponding entries of $X$.

Why is this objective linear?

If $X$ and $Y$ are matrices and $a,b$ are scalars, then

\[ \langle C,aX+bY\rangle =a\langle C,X\rangle+b\langle C,Y\rangle. \]

There are no products between unknown entries of $X$, no squares of those entries, and no eigenvalues in the objective. It is the matrix counterpart of a linear function $c^Tx$.

The same inner product also writes linear constraints. For example,

\[ \langle E_{11},X\rangle=1, \qquad \langle E_{22},X\rangle=1 \]

is simply another way to say $X_{11}=X_{22}=1$. Such equations cut an affine slice through the space of symmetric matrices.

What is the smallest complete example?

We already know the slice

\[ X= \begin{bmatrix} 1&t\\ t&1 \end{bmatrix}, \qquad X\succeq0, \]

contains exactly the values $-1\le t\le1$. We can ask for the smallest possible $t$ by writing

\[ \begin{aligned} \text{minimize}\quad &\langle S_{12},X\rangle\\ \text{subject to}\quad &\langle E_{11},X\rangle=1,\\ &\langle E_{22},X\rangle=1,\\ &X\succeq0. \end{aligned} \]

Read each line in the language already developed:

$X$ is the unknown symmetric matrix.
The objective equals $X_{12}=t$.
The two equalities fix the diagonal at one.
The PSD constraint limits the feasible slice to $-1\le t\le1$.

The optimizer is therefore

\[ X^\star= \begin{bmatrix} 1&-1\\ -1&1 \end{bmatrix}, \qquad \langle S_{12},X^\star\rangle=-1. \]

The objective does not curve or reshape the feasible interval. It assigns a score to every point and selects the point with the smallest score. Here that is the left endpoint, a rank-one boundary matrix.

What does the general form say?

Replace the two selector matrices by any collection $A_1,\ldots,A_m$, and replace the particular objective selector by any symmetric weight matrix $C$. The standard form is

\[ \begin{aligned} \text{minimize}\quad &\langle C,X\rangle\\ \text{subject to}\quad &\langle A_i,X\rangle=b_i, \qquad i=1,\ldots,m,\\ &X\succeq0. \end{aligned} \]

Here $C$, the matrices $A_i$, and the numbers $b_i$ are fixed problem data; $X$ is the decision variable. The objective is linear, the equalities carve out an affine slice, and the PSD condition keeps the slice inside the PSD cone. That combination is a semidefinite program. A maximization problem has the same form after negating $C$.

The notation $X\succeq0$ means that $X$ is PSD. It is one convex set constraint, rather than a separate linear inequality on each entry. An SDP can also be written with scalar variables inside an affine matrix inequality; later chapters will translate between the two descriptions.

Can a computer see the exact boundary?

The mathematical cone uses exact inequalities. A computer returns floating point eigenvalues, so a value such as -2e-10 needs a scale-aware tolerance and context. Clipping it to zero can be reasonable for recovering a Gram factor; silently declaring every small negative eigenvalue feasible is not. Chapter 09 develops this distinction into a complete solution audit.

We now have a feasible region, affine constraints, and a matrix inner product. The next chapter combines them into a complete SDP whose answer can also be checked analytically.

Try it yourself

Complete learner/03_the_psd_cone.jl.
Prove directly that $V V^T\succeq0$ for every rectangular matrix $V$.
Find a line through the $2\times2$ PSD cone whose feasible slice is a ray rather than a bounded interval.
For a diagonal matrix, describe its rank and whether it lies in the cone’s interior using only its diagonal entries.

--- title: "03. Where do PSD matrices live?" engine: julia julia: exeflags: ["--project=@."] --- Gram matrices give PSD matrices a geometric meaning. Optimization needs one more view: all $n\times n$ PSD matrices form a structured feasible region. ## What shape do all Gram matrices make? Take two PSD matrices from different vector configurations. Before calculating, predict whether every average between them will remain PSD. Then try to break the prediction by changing the mixing weight. ```{julia} #| label: combine-psd-matrices using LinearAlgebra X = [1.0 0.7; 0.7 1.0] Y = [2.0 -0.4; -0.4 0.5] for θ in (0.0, 0.25, 0.5, 0.75, 1.0) Z = θ * X + (1 - θ) * Y println("θ=$θ eigenvalues=", round.(eigvals(Symmetric(Z)); digits = 3)) end ``` The experiment suggests that the segment joining two PSD matrices stays PSD. Now name and prove the larger pattern. Write $$ \mathbb S_+^n=\{X\in\mathbb S^n:z^TXz\ge 0\text{ for every }z\in\mathbb R^n\}. $$ If $X,Y\succeq0$ and $a,b\ge0$, then $$ z^T(aX+bY)z=a z^TXz+b z^TYz\ge0. $$ Thus $aX+bY$ is PSD. Closure under nonnegative scaling makes the set a **cone**; closure under addition and averaging makes it **convex**. Convexity explains the experiment and gives optimization algorithms a connected, continuous region to move through. ::: {.callout-note title="Go further: theory and geometry"} Sections 1–3 of Vandenberghe and Boyd's survey develop SDP formulations, spectrahedra, and duality in more depth: [Semidefinite Programming](https://web.stanford.edu/~boyd/papers/sdp.html). MIT OpenCourseWare also provides a concise [semidefinite optimization lecture](https://ocw.mit.edu/courses/15-093j-optimization-methods-fall-2009/resources/mit15_093j_f09_lec23/). These are optional theory references; the course does not depend on their notation or organization. ::: A negative mixing weight can leave the cone, which explains why the failed attempt to break the pattern must violate $a,b\ge0$. What happens when a valid mixture approaches the cone's edge? ## What happens at the edge? A symmetric matrix is positive definite, written $X\succ0$, when every eigenvalue is strictly positive. These matrices form the interior of the PSD cone. A PSD matrix with at least one zero eigenvalue lies on the boundary. ```{julia} #| label: approach-cone-boundary for t in (0.0, 0.5, 0.9, 0.99, 1.0) M = [1.0 t; t 1.0] λ = eigvals(Symmetric(M)) println((t = t, λmin = minimum(λ), determinant = det(M), rank = rank(M))) end ``` Rank therefore records geometry and location at once. If $X=VV^T$, then `rank(X)` is the dimension needed by the represented vectors. Low-rank PSD matrices live on the cone's boundary. Later, exact cuts will correspond to the extreme case `rank(X) == 1`; the relaxation permits higher-dimensional geometry. ## What happens when constraints slice the cone? An SDP feasible set usually intersects the cone with affine equations. Such an intersection is called a **spectrahedron**. For example, $$ \left\{X\succeq0:X_{11}=X_{22}=1\right\} = \left\{\begin{bmatrix}1&t\\t&1\end{bmatrix}:-1\le t\le1\right\}. $$ The interval is not an analogy; it is literally a one-dimensional affine slice of $\mathbb S_+^2$. Its endpoints are rank-one boundary matrices. In three dimensions, fixing the diagonal to one gives the set of $3\times3$ correlation matrices. Pairwise entries cannot be chosen independently because the complete matrix must remain PSD. Chapter 04 optimizes over exactly that set. ## How do we optimize over matrices? In ordinary linear optimization, $c^Tx$ assigns a weight $c_i$ to each entry $x_i$ of a vector and adds the results. A matrix objective needs to do the same thing with entries $X_{ij}$. For two matrices of the same size, define $$ \langle C,X\rangle =\operatorname{tr}(C^TX) =\sum_{i,j}C_{ij}X_{ij}. $$ This is the **trace inner product**. Despite the name, the last expression shows the operation directly: multiply corresponding entries of $C$ and $X$, then add every product. The matrix $C$ contains the weights, and $X$ contains the quantities being chosen. ### How can a matrix select one entry? Suppose the decision matrix is symmetric: $$ X= \begin{bmatrix} X_{11}&X_{12}\\ X_{12}&X_{22} \end{bmatrix}. $$ To extract its upper-left entry, use $$ E_{11}= \begin{bmatrix} 1&0\\ 0&0 \end{bmatrix}, \qquad \langle E_{11},X\rangle=X_{11}. $$ Selecting an off-diagonal entry requires one extra detail. Both $X_{12}$ and $X_{21}$ appear in the entrywise sum, even though symmetry makes them equal. Put one half in each position: $$ S_{12}= \begin{bmatrix} 0&\tfrac12\\ \tfrac12&0 \end{bmatrix}, \qquad \langle S_{12},X\rangle =\tfrac12X_{12}+\tfrac12X_{21} =X_{12}. $$ The halves prevent the same symmetric entry from being counted twice. ```{julia} #| label: trace-inner-product using LinearAlgebra X_trial = [1.0 0.25; 0.25 1.0] E11 = [1.0 0.0; 0.0 0.0] E22 = [0.0 0.0; 0.0 1.0] S12 = [0.0 0.5; 0.5 0.0] @assert tr(S12' * X_trial) ≈ sum(S12 .* X_trial) (selected_off_diagonal = sum(S12 .* X_trial), first_diagonal = sum(E11 .* X_trial), second_diagonal = sum(E22 .* X_trial)) ``` The same operation can score a whole matrix, not merely select one entry. Different nonzero entries of $C$ assign different weights to the corresponding entries of $X$. ### Why is this objective linear? If $X$ and $Y$ are matrices and $a,b$ are scalars, then $$ \langle C,aX+bY\rangle =a\langle C,X\rangle+b\langle C,Y\rangle. $$ There are no products between unknown entries of $X$, no squares of those entries, and no eigenvalues in the objective. It is the matrix counterpart of a linear function $c^Tx$. The same inner product also writes linear constraints. For example, $$ \langle E_{11},X\rangle=1, \qquad \langle E_{22},X\rangle=1 $$ is simply another way to say $X_{11}=X_{22}=1$. Such equations cut an affine slice through the space of symmetric matrices. ### What is the smallest complete example? We already know the slice $$ X= \begin{bmatrix} 1&t\\ t&1 \end{bmatrix}, \qquad X\succeq0, $$ contains exactly the values $-1\le t\le1$. We can ask for the smallest possible $t$ by writing $$ \begin{aligned} \text{minimize}\quad &\langle S_{12},X\rangle\\ \text{subject to}\quad &\langle E_{11},X\rangle=1,\\ &\langle E_{22},X\rangle=1,\\ &X\succeq0. \end{aligned} $$ Read each line in the language already developed: - $X$ is the unknown symmetric matrix. - The objective equals $X_{12}=t$. - The two equalities fix the diagonal at one. - The PSD constraint limits the feasible slice to $-1\le t\le1$. The optimizer is therefore $$ X^\star= \begin{bmatrix} 1&-1\\ -1&1 \end{bmatrix}, \qquad \langle S_{12},X^\star\rangle=-1. $$ The objective does not curve or reshape the feasible interval. It assigns a score to every point and selects the point with the smallest score. Here that is the left endpoint, a rank-one boundary matrix. ### What does the general form say? Replace the two selector matrices by any collection $A_1,\ldots,A_m$, and replace the particular objective selector by any symmetric weight matrix $C$. The standard form is $$ \begin{aligned} \text{minimize}\quad &\langle C,X\rangle\\ \text{subject to}\quad &\langle A_i,X\rangle=b_i, \qquad i=1,\ldots,m,\\ &X\succeq0. \end{aligned} $$ Here $C$, the matrices $A_i$, and the numbers $b_i$ are fixed problem data; $X$ is the decision variable. The objective is linear, the equalities carve out an affine slice, and the PSD condition keeps the slice inside the PSD cone. That combination is a **semidefinite program**. A maximization problem has the same form after negating $C$. The notation $X\succeq0$ means that $X$ is PSD. It is one convex set constraint, rather than a separate linear inequality on each entry. An SDP can also be written with scalar variables inside an affine matrix inequality; later chapters will translate between the two descriptions. ## Can a computer see the exact boundary? The mathematical cone uses exact inequalities. A computer returns floating point eigenvalues, so a value such as `-2e-10` needs a scale-aware tolerance and context. Clipping it to zero can be reasonable for recovering a Gram factor; silently declaring every small negative eigenvalue feasible is not. Chapter 09 develops this distinction into a complete solution audit. We now have a feasible region, affine constraints, and a matrix inner product. The next chapter combines them into a complete SDP whose answer can also be checked analytically. ## Try it yourself 1. Complete `learner/03_the_psd_cone.jl`. 2. Prove directly that $V V^T\succeq0$ for every rectangular matrix $V$. 3. Find a line through the $2\times2$ PSD cone whose feasible slice is a ray rather than a bounded interval. 4. For a diagonal matrix, describe its rank and whether it lies in the cone's interior using only its diagonal entries.