# determinant of diagonal - fixed

I have to study/evaluate many determinants of the form $$f_M(J)=\det(J-M),$$ where $M$ is fixed, and $J$ is a diagonal matrix (with 0/1 on the diagonal, if it helps.) In my problem $M$ is fixed, and $J$ varies. Any suggestions?

-
Suggestion: Read mathoverflow.net/faq – Martin Brandenburg Apr 21 '12 at 10:28
Is $J$ perhaps varying slowly (one entry at a time)? Can we expect the number of zeros or ones in it to be small? Is $M$ sparse? How large is it more or less? – Federico Poloni Apr 21 '12 at 10:33
Use Gray codes and differential evaluation. Alternatively, determine the appropriate multilinear polynomial and evaluate it on the sequences of ones and zeros that are needed. Gerhard "Ask Me About System Design" Paseman, 2012.04.21 – Gerhard Paseman Apr 21 '12 at 20:37
This question is much too vague. I vote to close until the OP makes it clear what it is he is looking for. – Igor Rivin Apr 22 '12 at 0:37

Let $J$ be $\mathrm{diag}(a_1,...,a_n)$. Let $M_{i_1,...,i_k}$ be the principal submatrix of $M$ with rows and colums number $\{i_1,...,i_k\}$ deleted. Then $\det(J+M)=\det(M+\mathrm{diag}(0,a_2,...,a_n))+a_1\det(J_1+M_1)$ (expand along the first row). Thus $$\det(J+M)=\sum a_{i_1}\cdot\ldots\cdot a_{i_k} \det(M_{i_1,...,i_k}).$$ The sum is taken over all subsets of $\{1,...,n\}$. So if $M$ is fixed, your determinant is some polynomial in $a_1,...,a_n$ whose coefficients are principal minors of $M$. This is of course not difficult, but to continue, I would need to know what information about the determinant you want to get.
Update. By the way the same proof of course gives that coefficients of the characteristic polynomial of $M$ are (up to sign) sums of principal minors of $M$. This is a very useful fact, used, for instance, in one of the proofs of the classification of finite dimensional semi-simple Lie algebras (existence of Cartan subalgebras).
What running time? $M$ is supposed to be fixed. The only things (s)he needs to store are $a_i$, so he needs $n$ bytes of storage where $n$ is fixed. – Mark Sapir Apr 22 '12 at 3:30