The Determinant of a Sum of Matrices

Solution 1:

This is a straight-forward application of the linearity of the determinant on the rows of the matrix. Call the sum of the matrices $\Sigma_A$. Notice that each row of $\Sigma_A$ is a sum of the corresponding rows of each $A^i$. If we split the determinant along the first row, then we have $$\det\left(\Sigma_A\right) = \sum_{i=1}^N\det\left(\Sigma_A^{(i)}\right)$$ where each $\Sigma_A^{(i)}$ is the matrix obtained from $\Sigma_A$ by replacing the first row with the first row of $A^i$. Notice now that the second row (and on wards) of each $\Sigma_A^{(i)}$ remains a sum of rows. Splitting each $\Sigma_A^{(i)}$ along the second row now gives $$\det\left(\Sigma_A^{(i)}\right) = \sum_{j=1}^N\det\left(\Sigma_A^{(i,\,j)}\right)$$ where $\Sigma_A^{(i,\,j)}$ has first row of $A^i$ and second row of $A^j$. Substituting this new expression into our original summation, we have that $$\det\left(\Sigma_A\right) = \sum_{i=1}^N\sum_{j=1}^N\det\left(\Sigma_A^{(i,\,j)}\right)$$ or more compactly $$\det\left(\Sigma_A\right) = \sum_{(k_1,\ k_2)}\det\left(\Sigma_A^{(k_1,\,k_2)}\right)$$ Where the sum ranges over all $2$-tuples with $1\le k_1,\ k_2 \le N$. Continuing in the obvious fashion, we eventually reach $$\det\left(\Sigma_A\right) = \sum_{(k_1,\ \cdots, k_n)}\det\left(\Sigma_A^{(k_1,\,\cdots,k_n)}\right)$$ where the sum ranges over all $n$-tuples. Of course $\Sigma_A^{(k_1,\,\cdots,k_n)}$ is the matrix with row $i$ from $A^{k_i}$. This is exactly your desired sum.