Linear Functions on Symmetric Matrix Basis 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?
 A: 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$.
A: $\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.
