9
$\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$
8
  • $\begingroup$ Interesting question. How did you get this kind of matrices? $\endgroup$
    – ulead86
    Jun 1, 2015 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, 2015 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, 2015 at 12:38
  • 1
    $\begingroup$ @ulead86 This matrix comes up when one tries to find solutions for the puzzle "Lights Out". $\endgroup$
    – Martin
    Jun 1, 2015 at 14:02
  • 1
    $\begingroup$ Cross-posted to MO: Determinant of block tridiagonal matrices $\endgroup$
    – user1551
    Sep 21, 2015 at 22:13

1 Answer 1

Reset to default
3
$\begingroup$

Assume that $A \in M_{nk,nk}$. Then let $(P_n)$ be the sequences of matrices defined as follows

$$P_1=J_n, \qquad P_2={J_n}^2-I, \qquad 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(v*x-u, z, x); u := w end do; Digits := 1150;
Q := unapply(v, x); r := 1; for i to n do r := evalf(r*Q(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$
5
  • $\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, 2015 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, 2015 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, 2015 at 20:35
  • $\begingroup$ The residue mod 30 has nothing to do here. $\endgroup$
    – user91684
    Jun 4, 2015 at 21:06
  • $\begingroup$ @Martin Sorry to disturb you. I see that $\det(A)=0$ if $n+1$ is divisible by $5$ or $6$ because $\cos \dfrac{2\pi}{5} + \cos \dfrac{4\pi}{5} = -\dfrac{1}{2}$, $\cos \dfrac{3\pi}{6} + \cos \dfrac{4\pi}{6} = -\dfrac{1}{2}$. But can $\cos\dfrac{i\pi}{n+1} + \cos\dfrac{j\pi}{n+1} = -\dfrac{1}{2}$ for any other case? I asked because I saw you claiming in the MO link that you had solved this problem :) $\endgroup$
    – Jianing Song
    Feb 24 at 17:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .