5
$\begingroup$

From a homework assignment for an undergraduate course on numerical methods:

Check if the determinant of the following matrix is nonzero. \begin{bmatrix} 1 & -2 & 1 & & & & & \\ 1 & 4 & 1 & & & & & \\ & 1 & 4 & 1 & & & & \\ & & 1 & 4 & \ddots & & & \\ & & & \ddots & \ddots & \ddots \\ & & & & \ddots & 4 & 1 & & \\ & & & & & 1 & 4 & 1 & \\ & & & & & & 1 & 4 & 1 \\ & & & & & & 1 & -2 & 1 \end{bmatrix}

I tried using Laplace expansion but I think this leads to nothing. Is there another way to see regularity of such a "tridiagonal" matrix. Unfortunately, the matrix is not strictly diagonal dominant either. That is why I tried using Laplace but the submatrices I get from doing that are looking almost the same. Maybe one has another idea.

$\endgroup$
2
  • $\begingroup$ This problem arises from the not-a-knot condition in numerics. $\endgroup$ Commented 14 hours ago
  • $\begingroup$ Why not post a screenshot of the relevant section of the homework set? $\endgroup$ Commented 11 hours ago

2 Answers 2

Reset to default
3
$\begingroup$

I assume your $n\times n$ matrix, $M$, is sufficiently large -- in particular $n\geq 7$. You can directly calculate the determinant of $M$ when $n\leq 6$.

$\Sigma:=\begin{bmatrix} B & \mathbf 0 & \mathbf 0 \\ \mathbf 0 & I_{n-6} & \mathbf 0 \\ \mathbf 0 & \mathbf 0 & C \end{bmatrix}$ with

$B:=\begin{bmatrix} 1 & 0 & 0 \\ 0 & \frac{1}{3} & 0 \\ 0 & 0 & \frac{1}{3} \\ \end{bmatrix}$ and $C:=\begin{bmatrix} \frac{1}{3} & 0 & 0 \\ 0 & \frac{1}{3} & 0 \\ 0 & 0 & 1 \\ \end{bmatrix}$

$\implies \frac{1}{3^{4}}\cdot \det\big(M\big)=\det\big(M\Sigma\big)\neq 0$
where the right hand side holds by Taussky's refinement of Gerschgorin Discs since $(M\Sigma)$ is irreducible, weakly diagonally dominant and the dominance is strict in at least one row [row 4]. I gave a proof of Taussky's refinement under "Optional Second" here: Prove that this block matrix is positive definite

addendum: a different argument (assuming $n\geq 5$):
$M= H+S= \frac{1}{2}\big(M+M^T\big) +\frac{1}{2}\big(M-M^T\big)$
noting that the (i.) the Skew matrix is extremely sparse with its 1st column linearly independent amongst all other columns & the same holds for its nth column and (ii.) the Hermitian matrix is diagonally dominant with positive diagonals so $H\succeq \mathbf 0$-- i.e. for $\lambda \lt 0$ you have $(H-\lambda I)=(H+\vert \lambda\vert I)$ is strictly diagonally dominant so invertible and apply spectral theorem. (You could deduce irreducible $H\succ \mathbf 0$ by Taussky's refinement at this stage which then implies $\dim \ker M =0$ but I'll give a different approach.)

suppose that $\mathbf 0\neq \mathbf x \in \ker M$
$\implies \mathbf x^T H\mathbf x =0\implies \max\big(\vert x_1\vert, \vert x_n\vert\big)\gt 0 \text{ & }\mathbf x \in \ker H $ $\implies M\mathbf x = H\mathbf x +S\mathbf x =S\mathbf x \neq \mathbf 0 \text{ (contradiction)}$
the 1st implication holds since $\mathbf x^T H\mathbf x = \mathbf x^T M\mathbf x= 0$; the 2nd implication holds since the $n-2\times n-2$ middle principal submatrix of $H$ is strictly diagonally dominant with positive diagonals (i.e. is positive definite) & $H\succeq \mathbf 0$; finally $S\mathbf x \neq \mathbf 0$ by (i.) since the first and/or last component of $\mathbf x$ is not zero

$\endgroup$
2
  • $\begingroup$ This is pretty cool to be honest, but surley I'm not allowed to use this. $\endgroup$ Commented yesterday
  • 1
    $\begingroup$ As is your question is "missing context" since it tells us nothing about where this problem came from or what constraints you have on techniques involved. Since you evidently have unstated constraints but have indicated strict diagonal dominance is ok, consider modifying the above: e.g. do a couple row operations on $M$ so the 1st and last rows have three 2's [and rest all zero] use $B:=\begin{bmatrix} 1 & 0 & 0 \\ 0 & \frac{1}{2+\epsilon} & 0 \\ 0 & 0 & \frac{1}{2} \\ \end{bmatrix}$ for small $\epsilon\gt 0$ and similar for $C$. Then $M\Sigma$ would be strictly diagonally dominant. $\endgroup$ Commented yesterday
2
$\begingroup$

We can subtract the first row from the second row and the last row from the second-to-last row: $$ \begin{bmatrix} 1 & -2 & 1 & & & & & \\ 0 & 6 & 0 & & & & & \\ & 1 & 4 & 1 & & & & \\ & & 1 & 4 & \ddots & & & \\ & & & \ddots & \ddots & \ddots \\ & & & & \ddots & 4 & 1 & & \\ & & & & & 1 & 4 & 1 & \\ & & & & & & 0 & 6 & 0 \\ & & & & & & 1 & -2 & 1 \end{bmatrix} $$ Laplace expansion along the first column and then along the last column shows that the determinant of this matrix is equal to the determinant of $$ \begin{bmatrix} 6 & 0 & & & & \\ 1 & 4 & 1 & & & \\ & 1 & 4 & \ddots & & \\ & & \ddots & \ddots & \ddots \\ & & & \ddots & 4 & 1 & \\ & & & & 1 & 4 & 1 \\ & & & & & 0 & 6 \end{bmatrix} $$ That is a strictly diagonally dominant matrix, therefore its determinant is not zero.

One can even compute the determinant. Subtracting $1/6$ times the first row from the second row and $1/6$ times the second row from the second-to-last row shows that the determinant of the previous matrix is equal to that of the matrix $$ \begin{bmatrix} 6 & 0 & & & & \\ 0 & 4 & 1 & & & \\ & 1 & 4 & \ddots & & \\ & & \ddots & \ddots & \ddots \\ & & & \ddots & 4 & 1 & \\ & & & & 1 & 4 & 0 \\ & & & & & 0 & 6 \end{bmatrix} $$ and that is $6^2$ times the determinant of the tridiagonal Toeplitz matrix $$ T_n = \begin{bmatrix} 4 & 1 & & \\ 1 & 4 & \ddots & \\ & \ddots & \ddots & \ddots \\ & & \ddots & 4 & 1 \\ & & & 1 & 4 \end{bmatrix} $$ The determinant of $T_n$ can be computed using the recursion formula for the determinant of tridiagonal matrices: $$ \det T_0 = 0, \, \det T_1 = 4, \, \det T_n = 4 \det T_{n-1} - \det T_{n-2} $$ and an explicit formula is (see for example How to compute the determinant of a tridiagonal Toeplitz matrix?) $$ \det T_n = U_n(2) = \frac{(2+\sqrt 3)^{n+1}-(2-\sqrt 3)^{n+1}}{2 \sqrt 3} $$ where $U_n$ are the Chebyshev polynomials of the second kind.

So the determinant of your original matrix with $n \ge 4$ rows is $36 \cdot U_{n-4}(2)$.

$\endgroup$
0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.