1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ In the last trace equation, do you mean to have different bounds on the summations? Otherwise the trace sums are not equivalent. $\endgroup$ – pyrrhic Jan 7 '16 at 19:53
  • $\begingroup$ Yes, I meant to have different bounds. That's why you need the $2-\delta _{ij}$ term. $\endgroup$ – Michael Grant Jan 7 '16 at 19:54
  • $\begingroup$ Remember, $C_{ij}X_{ij} = C_{ji}X_{ji}$ here, due to symmetry. $\endgroup$ – Michael Grant Jan 7 '16 at 19:55
0
$\begingroup$

$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.