Proof of a fact about traces

I'm following the open courseware content on Machine Learning from Stanford University. In the lecture notes, it is given that

$$\Delta_A \ tr(ABA^TC) = CAB + C^TAB^T$$

which I tried but couldn't prove easily. It is not required to follow the course content but I just wondered and wanted to learn its proof. Any suggestions?

Update: $A$, $B$, and $C$ are matrices and $\Delta_A$ is the gradient operation on matrix $A$.

-
Dear Ismail: it's not necessary to open with a salutation or have a closing like "kind wishes". I guess $A$, $B$, $C$ are square matrices of the same size; could you say what is meant by $\Delta_A$ please? Also, a direct link to the lecture notes would be very nice. – Todd Trimble Feb 27 '11 at 16:56
Dear Todd: Thanks for you advice. I will take your remarks about how to ask a question into consideration. The course notes are here: stanford.edu/class/cs229/notes/cs229-notes1.pdf Page 9, Eq. 3. – İsmail Arı Feb 27 '11 at 17:07
I don't see the reason for getting a -1 for the question. Is that because I couldn't prove it easily? If so, why are there 8 current upvotes for the answer post. If I know the reason, I would update my questioning to mathoverflow community accordingly. – İsmail Arı Apr 10 '11 at 23:23
Also, btw, closing with "kind wishes" does not disturb me in the least! – paul garrett Apr 21 at 1:21
Denis Serre edited into the question the following, which should be left as a comment or answer: "In standard mathematics, where the gradient is denoted $\nabla$, the formula should be $$\nabla_A {\rm Tr}(ABA^TC) = CAB + C^TAB^T.$$ Using the even more intrinsic notion of differential, this writes $${\rm D}_A {\rm Tr}(ABA^TC)\cdot M ={\rm Tr} (CAB + C^TAB^T)^TM.$$ The proof of it is pretty obvious, because of bilinearity, and does not require calculating with indices!" – Todd Trimble Apr 21 at 7:55

I guess $\Delta_A$ denotes the derivative with respect to the elements of the matrix $A$ (more conventionally denoted by $\partial_{A}$).

To evaluate the derivative with respect to $A_{ij}$, write out the trace in terms of components and then use $\partial_{A_{ij}} A_{mn} = \delta_{im} \delta_{jn}$, $$\partial_{A_{ij}} \text{tr}(A B A^T C) = \partial_{A_{ij}}\sum_{mnkl} A_{mn} B_{nk} A_{lk} C_{lm}= \sum_{kl} B_{jk}A_{lk} C_{li} + \sum_{mn} A_{mn} B_{nj} C_{im}$$ $$= ( C^T A B^T+ C A B )_{ij}.$$ This is the component-wise version of your identity.

Note to the comment of Todd Trimble: the matrices $A,B$, and $C$ do not have to be necessarily square matrices. Their dimension just has to "match" ($A \in \mathbb{R}^{m \times n}$, $B\in \mathbb{R}^{n \times n}$, $C \in \mathbb{R}^{m \times m}$, with $m$ and $n$ arbitrary integers).

-
Dear Fabian: Your guess is correct. Sorry for missing definition. The operator in question is the gradient operation as you guessed. – İsmail Arı Feb 27 '11 at 17:14

I'm going to decompose Fabian's answer into something a little more newb friendly. An important concept is the partial derivative of a matrix with respect to one of its elements. An example of this is

$$\partial_{\mathbf{A}_{31}} \mathbf{A} = \partial_{\mathbf{A}_{31}} \begin{bmatrix} \mathbf{A}_{11} & \mathbf{A}_{12} \\ \mathbf{A}_{21} & \mathbf{A}_{22} \\ \mathbf{A}_{31} & \mathbf{A}_{32} \end{bmatrix} = \begin{bmatrix} 0 & 0 \\ 0 & 0 \\ 1 & 0 \end{bmatrix}.$$

In general, if we take the derivative with respect to the $(i,j)$ entry, then the $(m,n)$ entry of the resulting matrix is

$$\partial_{A_{ij}} A_{mn} = \delta_{im} \delta_{jn}$$ where $\delta$ is the Kronecker delta. This is simply the basic statement of multivariate calculus: namely $\partial_x x = 1$ and $\partial_x y = 0$. In particular,

\begin{align*} \sum_{mn} \partial_{A_{ij}} A_{mn} = \partial_{A_{ij}} A_{ij} = 1. \qquad \text{(1)} \end{align*}

To begin the proof, we consider matrix equations, which are

\begin{align*} \partial_{\mathbf{A}} \text{tr}(\mathbf{A} \mathbf{B} \mathbf{A}^\text{T} \mathbf{C}) &= \partial_{\mathbf{A}} \sum_{m} \left(\mathbf{A} \mathbf{B} \mathbf{A}^\text{T} \mathbf{C}\right)_{mm} \qquad \text{(Trace[2])} \\ &= \partial_{\mathbf{A}} \sum_{m} \Bigg(\sum_{n k \ell} A_{mn} B_{nk} \left(A^T\right)_{k \ell} C_{\ell m}\Bigg)_{mm} \qquad \text{ (Matrix multiplication [3])} \\ &= \partial_{\mathbf{A}} \sum_{m n k \ell} A_{mn} B_{nk} A_{ \ell k} C_{\ell m} \qquad \text{ (Transpose [4])} \\ &= \mathbf{C}^T \mathbf{A B}^T + \mathbf{C A B}, \end{align*}

where we justify the last step component-wise. For all elements $(i,j)$, it follows that

\begin{align*} &\Bigg( \partial_{\mathbf{A}} \sum_{m n k \ell} A_{mn} B_{nk} A_{ \ell k} C_{\ell m} \Bigg)_{ij} \\ &= \partial_{\mathbf{A}_{ij}} \sum_{m n k \ell} A_{mn} B_{nk} A_{ \ell k} C_{\ell m} \qquad \text{(Scalar-by-matrix derivative[5])} \\ &= \sum_{mnk \ell} \partial_{A_{ij}} A_{mn} B_{nk} A_{ \ell k} C_{\ell m} \qquad \text{ (Linearity of differentiation [6])} \\ &= \sum_{mnk \ell} (\partial_{A_{ij}} A_{mn}) (B_{nk} A_{\ell k} C_{\ell m}) + (A_{mn}) (\partial_{A_{ij}} B_{nk} A_{\ell k} C_{\ell m}) \qquad \text{(Product Rule[7])} \\ &= \sum_{mnk \ell} (\partial_{A_{ij}} A_{mn}) B_{nk} A_{\ell k} C_{\ell m} + \sum_{mnk \ell} A_{mn} (\partial_{A_{ij}} B_{nk} A_{\ell k} C_{\ell m}) \\ &= \sum_{k \ell} B_{jk} A_{\ell k} C_{\ell i} + \sum_{mnk \ell} A_{mn} (\partial_{A_{ij}} B_{nk} A_{\ell k} C_{\ell m}) \qquad \text{ (Eqn. 1)} \\ &= \sum_{k \ell} B_{jk} A_{\ell k} C_{\ell i} + \sum_{mnk \ell} A_{mn} \Big[(\partial_{A_{ij}} A_{\ell k}) (B_{nk} C_{\ell m}) + (A_{\ell k}) (\partial_{A_{ij}} B_{nk} C_{\ell m})\Big] \text{ (Product R.)} \\ &= \sum_{k \ell} B_{jk} A_{\ell k} C_{\ell i} + \sum_{mnk \ell} A_{mn} (\partial_{A_{ij}} A_{\ell k}) B_{nk} C_{\ell m} \\ &= \sum_{k \ell} B_{jk} A_{\ell k} C_{\ell i} + \sum_{mn} A_{mn} B_{nj} C_{i m} \qquad \text{ (Eqn. 1)} \\ &= \sum_{k \ell} C_{\ell i} A_{\ell k} B_{jk} + \sum_{mn} C_{i m} A_{mn} B_{nj} \\ &= \sum_{k \ell} \left(C^T\right)_{i \ell} A_{\ell k} \left(B^T\right)_{kj} + \sum_{mn} C_{im} A_{mn} B_{nj} \qquad \text{(Transpose)} \\ &= \left( \mathbf{C}^T \mathbf{A} \mathbf{B}^T + \mathbf{C} \mathbf{A} \mathbf{B} \right)_{ij}, \qquad \text{(Matrix multiplication)} \end{align*}

which completes the proof.

-