How to efficiently compute the determinant of a matrix with unknown diagonal entries?

Question

I would like to ask Python to compute the determinant of a large symmetric matrix where all off diagonal entries are known. The diagonal entries could vary. Since I need to compute the determinant many times with different diagonal entries, it seems a waste of time when the computation involves the multiplications of all those known entries over and over again. Is there a way to pre-compute the determinant so that it is a function of diagonal entries with some prefactors?

Answer 1

I don't think that this is very efficient but it does determine algebraically what the algebraic form of the answer looks like.

Suppose that your matrix is $A=[a_{ij}]_{i,j=0}^n$, and that $x_i:=a_{ii}$.

Then the determinant is some polynomial $$ \Delta=\sum_{i_1<i_2<\dots<i_k}\alpha_{i_1 i_2 \dots i_k}\ x_{i_1}x_{i_2}\dots x_{i_k} $$ where the sum is running over all the $2^n$ subsets of $\{1,2,\dots,n\}$.

How can we determine the coefficients $\alpha_{i_1 i_2 \dots i_k}$?

Well note first that from the polynomial expansion we have that $$ \alpha_{i_1 i_2 \dots i_k} =\frac{\partial^k\Delta}{\partial x_{i_1}\partial x_{i_2}\dots\partial x_{i_k}}\big|_{x_1=x_2=\dots=x_n=0}. $$

Now we can differentiate $\Delta$ using the shape of $A$. Consider the usual expansion of $\Delta$ by the $j$-th row. Then we see that differentiating with respect to $x_j$ essentially replaces the $j$-row of $\Delta$ by a row which is $0$ everywhere except at the $j$-th column, where it is $1$.

Hence we obtain the coefficient $\alpha_{i_1 i_2 \dots i_k}$ by replacing in $A$ the rows $i_1, i_2, \dots, i_k$ as above, then setting all the $x_i=0$, and computing the determinant. Effectively we are just computing the cofactor got by deleting these rows of $A$ after setting the diagonal entries to $0$.

[There may be hidden conventions here: to avoid doubt, the constant term is $\alpha_{\emptyset}$ and it is just the determinant of $A$ after setting the diagonal terms to $0$; and the coefficient $\alpha_{1 2 \dots n}$ of $x_1 x_2\dots x_n$ is $1$.]