Why $x^TAx=\text{Tr}(AX)$?

Question

In many optimization resources, when we reformulate an LP to an SDP, we sometimes use the fact that \begin{equation*} x^{T}Ax = Tr(AX), \end{equation*} where $X=xx^T$ is a number. But when I tried to derive the equation, I can't get the desired result. Namely, \begin{equation*} x^{T}Ax = \sum_{j=1}^{n}\sum_{i=1}^{n}a_{i,j}x_ix_j, \end{equation*} and \begin{equation*} Tr(AX) = (a_{1,1}+...+a_{n,n})(x_1^2+...+x_n^2). \end{equation*} The two polynomials are clearly different: simply, $a_{1,1}x_2^2$ is a term in the second polynomial but not in the first one. Please point out where I missed, thanks!

Answer 1

You've confused $xx^T$ with $x^Tx$, or else you've assumed $x$ is a row vector instead of a column vector. Either way, $A$ is being multiplied with a square matrix of the same shape. So the proof is $x_iA_{ij}x_j=A_{ij}x_jx_i=A_{ij}X_{ji}$.

Answer 2

The two parts are that a one by one matrix is its own trace, so that $x^T Ax= \operatorname{trace} x^TAx .$ Next $ \operatorname{trace} EF = \operatorname{trace} FE $ when multiplication is defined in both orders. Finally, this does not give arbitrary orders with three terms, just cyclic, so that $$ \operatorname{trace} EFG = \operatorname{trace} FGE = \operatorname{trace} GEF $$ so that $$ \operatorname{trace} x^T A x = \operatorname{trace} A x x^T = \operatorname{trace} x x^T A $$