Formula for the gradient of $f(A) = u^TA^kv$ Given a function of the form 
$$f(A) = u^TA^kv,$$
where $A$ is an $n\times n$ real-valued matrix, $u$ and $v$ are real vectors, and $k$ is some positive integer power.  
Does there exist a general formula for the gradient/partial derivatives $\displaystyle\frac{\partial f}{\partial a_{ij}}$ of $f$?
 A: I am assuming that the vectors $u$ and $v$ do not depend on $A$. According to The Matrix Cookbook ( https://www.math.uwaterloo.ca/~hwolkowi/matrixcookbook.pdf )
$$\partial(u^\top A^k v) = u^\top \partial (A^k) v.$$
Now, the book doesn't give $\partial(A^k)$ explicitly. However, you can look at $\partial(A^k)$ for small values of $k$, and prove by induction that $$\partial(A^k) = \sum_{\ell=0}^{k-1} A^\ell \cdot \partial A \cdot A^{k-\ell-1}.$$
Substituting this into our equation yields 
$$\partial(u^\top A^k v) =\sum_{\ell=0}^{k-1} u^\top A^\ell \cdot \partial A \cdot A^{k-\ell-1}v$$
and thus
$${\partial(u^\top A^k v)\over \partial A_{i,j}} =\sum_{\ell=0}^{k-1} u^\top A^\ell \cdot {\partial A\over \partial A_{i,j}} \cdot A^{k-\ell-1}v.$$
Lastly, $${\partial A \over \partial A_{i,j}}=J(i,j),$$ where $J$ is the matrix whose only nonzero entry is $J(i,j)_{i,j} = 1$. (Hence, if $n=2$, $J(1,2)=\pmatrix{0&1\cr 0&0\cr}$.) This gives us
$${\partial f\over \partial A_{i,j}} =\sum_{\ell=0}^{k-1} u^\top A^\ell \cdot J(i,j) \cdot A^{k-\ell-1}v.$$
In the words of Farish Odish, "There is a positive probability that this answer is correct." 8-)
