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

  • 4
    $\begingroup$ 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. $\endgroup$ – Todd Trimble Feb 27 '11 at 16:56
  • 1
    $\begingroup$ 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. $\endgroup$ – İsmail Arı Feb 27 '11 at 17:07
  • 2
    $\begingroup$ 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. $\endgroup$ – İsmail Arı Apr 10 '11 at 23:23
  • 3
    $\begingroup$ Also, btw, closing with "kind wishes" does not disturb me in the least! $\endgroup$ – paul garrett Apr 21 '16 at 1:21
  • 2
    $\begingroup$ 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!" $\endgroup$ – Todd Trimble Apr 21 '16 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).

  • $\begingroup$ Dear Fabian: Your guess is correct. Sorry for missing definition. The operator in question is the gradient operation as you guessed. $\endgroup$ – İ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.


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.