Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
    
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... –  Igor Rivin Apr 22 '12 at 2:53
1  
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
    
Thank you very much, this looks quite interesting. –  user21541 Apr 22 '12 at 9:14
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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