Why is function $X \mapsto z^T X z$ linear?

Question

From Boyd & Vandenberghe's Convex Optimization:

$\textsf{Example 2.7}\;\;$ The positive semidefinite cone $\mathbf{S}_+^n$ can be expressed as

$$ \bigcap_{z\not=0} \{ X \in \mathbf{S}^n \mid z^TXz \geq 0 \}. $$

For each $z \not= 0$, $z^TXz$ is a (not identically zero) linear function of $X$, so the sets

$$ \{ X \in \mathbf{S}^n \mid z^TXz \geq 0 \} $$

are, in fact, halfspaces in $\mathbf{S}^n$. Thus the positive semidefinite cone is the intersection of an infinite number of halfspaces, and so is convex.

_{[Printscreen]}

---

Why is $z^T X z$ a linear function in matrix $X$? I don't understand what to do when the variable is a matrix.

Answer 1

Because your matrix $X$ is like a container of variables, and you can write :

$$z^\top X z = \sum_{i=1}^N \sum_{j=1}^N z_i z_j X_{ij}$$

As you can see, the function $f(X)$ is linear in the variables $X_{ij}$ which are contained in $X$.

Answer 2

$$ {\bf X} \mapsto {\bf z}^\top {\bf X} \, {\bf z} = \mbox{tr} \left( {\bf z}^\top {\bf X} \, {\bf z} \right) = \mbox{tr} \left( {\bf z} \, {\bf z}^\top {\bf X} \right) = \langle {\bf z} \, {\bf z}^\top , {\bf X} \rangle$$

where the Frobenius inner product is used.

Answer 3

The key point to note is that the quadratic form $z^T X z$ is linear in $X$ (to be explicit, it is not linear in $z$). To verify this, the additivity and homogeneity tests yield:

(i) $z^T (X + Y) z = z^TXz + z^TYz$

(ii) $z^T (\alpha X)z = \alpha (z^TXz)$ which helps us conclude that the given expression is indeed linear in $X$.