3
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Suggestion: Read mathoverflow.net/faq $\endgroup$ Apr 21, 2012 at 10:28
  • $\begingroup$ 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? $\endgroup$ Apr 21, 2012 at 10:33
  • $\begingroup$ 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 $\endgroup$ Apr 21, 2012 at 20:37
  • $\begingroup$ This question is much too vague. I vote to close until the OP makes it clear what it is he is looking for. $\endgroup$
    – Igor Rivin
    Apr 22, 2012 at 0:37

1 Answer 1

3
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ In most applications an exponential running time (and storage) algorithm is viewed as bad, but of course it is not clear what the OP is looking for... $\endgroup$
    – Igor Rivin
    Apr 22, 2012 at 2:53
  • 1
    $\begingroup$ 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. $\endgroup$
    – user6976
    Apr 22, 2012 at 3:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.