8
$\begingroup$

Is there a formula to compute the determinant of block tridiagonal matrices, when the determinants of the involved matrices are known? In particular, I am interested in the case

$$A = \begin{pmatrix} J_n & I_n & 0 & \cdots & \cdots & 0 \\ I_n & J_n & I_n & 0 & \cdots & 0 \\ 0 & I_n & J_n & I_n & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & \ddots & 0 \\ 0 & \cdots & \cdots & I_n & J_n & I_n \\ 0 & \cdots & \cdots & \cdots & I_n & J_n \end{pmatrix}$$

where $J_n$ is the $n \times n$ tridiagonal matrix whose entries on the sub-, super- and main diagonals are all equal to $1$ and $I_n$ is identity matrix of size $n$.

$\endgroup$
  • $\begingroup$ Interesting question. How did you get this kind of matrices? $\endgroup$ – ulead86 Jun 1 '15 at 11:22
  • $\begingroup$ You may be interested in this related paper. Otherwise, you can probably adapt the recurrence relation used to compute the determinant of tridiagonal matrices. $\endgroup$ – A.P. Jun 1 '15 at 12:23
  • 1
    $\begingroup$ Is $A$ an $n^2\times n^2$ matrix or is the number of blocks in $A$ somehow parameterized ($kn\times kn$)? In the first case, you can use the Kronecker product: $A=I_n\otimes K_n+K_n\otimes I_n+I_{n^2}$, where $K_n=J_n-I_n$. There is an analytic expressions for the eigenvalues of $K_n$ (Toeplitz tridiagonal matrix). $\endgroup$ – Algebraic Pavel Jun 1 '15 at 12:38
  • $\begingroup$ @A.P. thank you for mentioning the paper. If I use this result, I need to compute powers of $J$. Is anything known about that? $\endgroup$ – Martin Jun 1 '15 at 13:59
  • 1
    $\begingroup$ @ulead86 This matrix comes up when one tries to find solutions for the puzzle "Lights Out". $\endgroup$ – Martin Jun 1 '15 at 14:02
2
$\begingroup$

Assume that $A\in M_{nk,nk}$. Then let $(P_n)$ be the sequences of matrices defined as follows: $P_1=J_n,P_2={J_n}^2-I,P_q=J_nP_{q-1}-P_{q-2}$.

Then $\det(A)=\det(P_k)$.

EDIT. The eigenvalues of $J_n$ are the $(1+2\cos(\pi \dfrac{p}{n+1})),p=1\cdots n$; thus, if $Q$ is any polynomial, then we can calculate approximations of the eigenvalues of $Q(J_n)$, and then, an approximation of $\det(A)$. When we have enough significant digits, we deduce the true result -because this one is an integer-. Finally, we do not need to calculate any product of matrices. That follows calculates -using Maple- $\det(A)$ when $n=k=100$ (duration of the calculation: $1$"). First step. You choose Digits:=30. You see that the result has $1076$ digits. Second step. You choose Digits:=1150 and that works (see the sequence of zeros (or eventually of $9$) that appears at the end of the development of the obtained decimal number).

restart; with(LinearAlgebra): k := 100; n := 100; d := time(); B := Matrix(n, n); for i to n do B[i, i] := 1 end do; for i to n-1 do B[i, i+1] := 1; B[i+1, i] := 1 end do; z := CharacteristicPolynomial(B, x); u := x; v := x^2-1; for i from 3 to k do w := v; v := rem(vx-u, z, x); u := w end do; Digits := 1150; Q := unapply(v, x); r := 1; for i to n do r := evalf(rQ(1+2*cos(i*Pi/(n+1)))) end do; print(r); time()-d;

$2.44387846087090290145607732170537391377490420405227812708050615\\ 28277319341932844677382952399933460059814926416716644013099963\\ 42708968356667589737763656457680692376518632271970928028188495\\ 28837548232087652163820090152818313133799717624970641029956038\\ 21298982012250961831581518578716473316074214193004344884914447\\ 80091522565037919891219503197811771573350002012798682732589728\\ 91073456252754229360553614557394171698663316722024355474750138\\ 99058808405660398400447542745412413310559180910765198835081950\\ 16753460456828320406836683930343030087726159407318434195928328\\ 91168720495008933297278988838511004283717390785348840943983494\\ 94573265138514209244141811048121198105502888315873129747553394\\ 28745956498781145738030840450505861505489488623215771119102138\\ 24860932438498432031584839888927118146735452787049842756602723\\ 13071431049603803135820994521439844817046772204723218141987299\\ 65625418270767015593634878034477052797174424114584736827230518\\ 99846006803088990947026408309411889789175194098825709435984858\\ 82242334251648224773936990898407542151092941240200527201190067\\ 27465966535881736354100000000000000000000000000000000143203220\\ 133487059755244617410791395080\times 10^{1075}$

$\endgroup$
  • $\begingroup$ Is there a way to compute the determinant of $P_n$ if the determinants of $P_k$ are known for $1 \leq k < n$? In other words: does this give a recursive formula for $\det(A)$? $\endgroup$ – A.P. Jun 2 '15 at 15:01
  • $\begingroup$ This recursion is essentially the same as in the paper mentioned by A.P. So again one has to compute (sums of) powers of $J_n$. Do you know anything about these powers? $\endgroup$ – Martin Jun 2 '15 at 16:19
  • $\begingroup$ Thanks for your edit. This is a good start for me :) However, a closed formula for $\det(A)$ would be nice. (It seems, that it depends only on the residue class of $n$ modulo $30$ if $\det(A)$ is nonzero). So if anyone knows something more, i would be grateful. $\endgroup$ – Martin Jun 4 '15 at 20:35
  • $\begingroup$ The residue mod 30 has nothing to do here. $\endgroup$ – loup blanc Jun 4 '15 at 21:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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