Linear Functions on Symmetric Matrix Basis

Question

I don't really understand this comment at the end of Boyd's Convex Optimization, Section 1.6.

In the following, $S^k$ represents the space of $k \times k$ symmetric matrices.

"We usually leave it to the reader to translate general results or statements to other vector spaces. For example, any linear function $f : R^n → R$ can be represented in the form $f(x) = c^T x$, where $c \in R^n$. The corresponding statement for the vector space $S^k$ can be found by choosing a basis and translating. This results in the statement: any linear function $f : S^k \to R$ can be represented in the form $f(X) = tr(CX)$, where $C \in S^k$."

Can anyone explain the last two sentences? Why does the $tr(CX)$ function sufficiently capture all possible linear functions on symmetric matrices?

Answer 1

Well, write out the matrix multiplication, with a little trick to take advantage of the fact that $C=C^T$ or $X=X^T$: $$[CX]_{ij} = [C^TX]_{ij} = \sum_{k=1}^n C_{ik} X_{jk}, \quad 1\leq i,j\leq n$$ Now take the trace: $$\mathop{\textrm{Tr}}(CX) = \sum_{i=1}^n [CX]_{ii} = \sum_{i=1}^n \sum_{j=1}^n C_{ij} X_{ij}$$ Now exploit symmetry: $$\mathop{\textrm{Tr}}(CX) = \sum_{i=1}^n \sum_{j=i}^n (2-\delta_{i-j}) C_{ij} X_{ij}$$ where $\delta_{i-j}=1$ if $i=j$ and $0$ otherwise. In other words, the $2-\delta_{i-j}$ term just represents the fact that off-diagonal elements are appearing twice in the sum, versus once for the diagonal elements.

What we see is that $\mathop{\textrm{Tr}}(CX)$ is certainly a linear function of $X$---double $X$, and you double its value. Furthermore, every unique element of $X$ is represented, and multiplied by an independent element of $C$: $C_{ij}=C_{ji}$ multiplies $X_{ij}=X_{ji}$, and that's it.

So yes, you can represent every possible linear function on the symmetric matrices by choosing appropriate symmetric coefficient matrices $C$.

Answer 2

$\mathbb R^{k(k+1)/2}$ and $S^k$ are equivalent vector spaces: any symmetric $k\times k$ matrix can be uniquely identified with a vector in $\mathbb R^{k(k+1)/2}$. The correspondence can be seen by listing the upper-triangular and diagonal $k(k+1)\over 2$ entries of the matrix as a vector in $\mathbb R^{k(k+1)/2}$.

The inner product of two vectors in $\mathbb R^{k(k+1)/2}$ is the sum of the component-wise products of the two vectors. For two matrices, this will be the sum of the component-wise products of the entries (again, one can see this in terms of turning the matrices into vectors in $\mathbb R^{k(k+1)/2}$). This is achieved for matrices by the product $tr(CX)$.

A real-valued linear mapping on $\mathbb R^{k(k+1)/2}$ is uniquely characterised by some vector $c$; it's action is to map each vector $x\in \mathbb R^{k(k+1)/2}$ to a real number by the inner product $c^{T}x$. So, simply convert $c$ to its corrresponding matrix representation $C$, $x$ to $X$, and the observation becomes clear.