Let $A$ be a square matrix with non-negative elements. Let $n$ be a positive integer. How to evaluate the following for all possible $n$?
$$f_{n}(A, i, j) = \frac{\partial }{\partial A_{ij}}\left(\vec{1}A^{n}\vec{1}^{\intercal}\right)$$
where $\vec{1}$ is a row vector and $\vec{1}^{\intercal}$ is transpose of $\vec{1}$.
Attempt to solve
I thought
$$f_{3}(A, i, j) =\vec{1}(BAA + ABA +AAB)\vec{1}^{\intercal}$$
where
$$B_{i'j'} = \begin{cases} 1, & i = i', j=j' \\ 0, &\text{otherwise}\end{cases}$$
But the problem is that the expression is always non-negative.
Unless the function is monotonic, I would not expect the first derivative to always have the same sign.
What is the correct answer?
The trace/Frobenius product, i.e. $$A:B={\rm Tr}(A^TB)$$ makes the derivation a bit easier, but won't be needed in the final result.
Write the inner function in terms of this product.
Then find its differential and gradient. $$\eqalign{ \phi &= 1^TA^n1 = 11^T:A^n \cr d\phi &= 11^T:dA^n \cr &= 11^T:\sum_{k=1}^{n} A^{k-1}\,dA\,A^{n-k} \cr &= \sum_{k=1}^{n} \Big(A^{k-1}11^TA^{n-k}\Big)^T:dA \cr \frac{\partial\phi}{\partial A} &= \sum_{k=1}^{n} \Big(A^{k-1}11^TA^{n-k}\Big)^T \cr }$$ To extract the $(i,j)^{th}$ element, multiply by the $(e_i,e_j)$ vectors from the standard basis $$\eqalign{ f_n(A,i,j) &= e_i^T\,\Big(\frac{\partial\phi}{\partial A}\Big)\,e_j \cr &= \sum_{k=1}^{n} e_i^T\Big(A^{k-1}11^TA^{n-k}\Big)^Te_j \cr &= \sum_{k=1}^{n} e_j^T\,A^{k-1}11^TA^{n-k}\,e_i \cr &= \sum_{k=1}^{n} 1^TA^{n-k}\,e_ie_j^T\,A^{k-1}1 \cr &= 1^T\bigg(\sum_{k=1}^{n} A^{n-k}\,e_ie_j^T\,A^{k-1}\bigg)1 \cr }$$