8
$\begingroup$

I have found the determinant of the following matrix of order $n\ge3$ using some elemetary operations $$\begin{bmatrix}0& 1 & 1& \dots & 1 \\ 0 & 0 & 1& \ddots & 1\\ 1 & 0 & 0 & \ddots & 1 \\ \vdots & \ddots & \ddots & \ddots & 1 \\ 1 & 1 & 1 & \dots & 0 \end{bmatrix}_{n\times n},$$ that is, a matrix which have diagonal, subdiagonal entries zero and rest of entries are equal to 1. Its determinant comes out to be equal to $$(-1)^n\Big(\lfloor\frac{n-2}{2}\rfloor\Big),$$ where, $\lfloor.\rfloor$ is the floor function. Now, I want to find determinant of the following matrix $$ \begin{bmatrix}0& -1 & 1& \dots & 1 \\ 0 & 0 & -1& \ddots & 1\\ 1 & 0 & 0 & \ddots & 1 \\ \vdots & \ddots & \ddots & \ddots & -1\\ 1 & 1 & 1 & \dots & 0 \end{bmatrix}_{n\times n},$$ that is, a matrix having diagonal and subdiagonal entries zero. Superdiagonal elements are -1 and rest of the entries are equal to 1.

$\endgroup$
  • $\begingroup$ Does $0,0,1,3,6,2,15,53,44,92,349,503,802,2310,4347$ match your calculations? $\endgroup$ – Douglas Zare Mar 9 '17 at 3:01
  • $\begingroup$ Yes, you are correct. Please let me know the steps. $\endgroup$ – Ranveer Singh Mar 9 '17 at 3:13
  • $\begingroup$ I don't know the pattern. It's not in the OEIS yet. I just asked Mathematica to compute the first few values and thought they might be helpful to others. $\endgroup$ – Douglas Zare Mar 9 '17 at 4:54
9
$\begingroup$

Here is a principal solution (some details left for you).

Let $A$ be an $n\times n$ tridiagonal matrix such that all its entries consisting of zeros except for those on (i) the main and subdiagonals are $-1$; (ii) superdiagonals are $-2$.

Let $u$ be the column vector all entries are $1$ so that $uu^T$ is an $n\times n$ matrix of all $1$'s. This way, your matrix becomes $A+uu^T$. Now, apply the Matrix Determinant Lemma to obtain $$\det(A+uu^T)=(1+u^TA^{-1}u)\cdot\det(A).$$ The good news is: determinants and inverses of tridiagonal matrices are calculable (see this on Wiki). For example, in the present case $$f_n:=\det(A)=(-1)^n\sum_{k=0}^{\lfloor\frac{n}2\rfloor}(-1)^k\binom{n-k}k2^k.$$ Also, observe that the quantity $u^TA^{-1}u$ is the sum of all entries of the inverse matrix $A^{-1}$.

UPDATE. Since you still ask about the inverse and etc, I've computed your determinant \begin{align} \det(A+uu^T)&=f_n+\sum_{i\leq j}^{1,n}2^{j-i}f_{i-1}f_{n-j}+\sum_{j<i}^{1,n}f_{j-1}f_{n-i} \\ &=f_n+\sum_{i=1}^nf_{i-1}f_{n-i}+\sum_{j<i}^{1,n}(1+2^{i-j})f_{j-1}f_{n-i}. \end{align}

$\endgroup$
  • $\begingroup$ I am trying to solve the recurrence relations for determinant and inverse of A using characteristic equation. Your expression for determinant is more simpler and fancy, but I do not know how you arrived to this expression?. It will be better for me if you elaborate this or provide me some references where I can read about such solutions. $\endgroup$ – Ranveer Singh Mar 9 '17 at 9:53
  • $\begingroup$ Very nice! Do you suppose a non-recursive formula is possible? $\endgroup$ – Felix Goldberg Mar 9 '17 at 10:15
  • $\begingroup$ One more thing. I have found the determinant of A using characteristic equation of recurrence relation. But, in order to calculate inverse of A, I need to solve a recurrence of function \phi, where each \phi depends on higher index \phi. So, I don't think characteristic equation is good way to solve \phi. That is why I am more interested in your way of solving recurrence. $\endgroup$ – Ranveer Singh Mar 9 '17 at 13:08
  • $\begingroup$ Denoting $\det(A)$ by $f(n)$, we also have the recurrence $$ f(n)=-f(n-1)-2f(n-2). $$ $\endgroup$ – Richard Stanley Mar 9 '17 at 17:03
  • $\begingroup$ @RichardStanley, I have already solved the recurrence for f(n). I was hoping for some expression for inverse of A, like expression for det of A given in above answer. $\endgroup$ – Ranveer Singh Mar 9 '17 at 19:22
3
$\begingroup$

I will try to give a different explicit solution. From the problem formulation of answer 1, $$\det(A+uu^T)=(1+u^TA^{-1}u).\det(A).$$ From here, we need to solve some recursive expressions, in order to calculate the determinant and inverse of $A$. I solve these recursive expressions using roots of their characteristic equations. For the determinant of $A$, recursive expression is $$f_n=-f_{n-1}-2f_{n-2},\ \ \ \ \ f_0=1,\ f_{-1}=0.$$ Roots of the resulting characteristic equation $x^2+x+2=0,$ are $$ s_1=\frac{-1}{2}+ \frac{\iota \sqrt{7}}{2},\ \ s_2=\frac{-1}{2}- \frac{\iota \sqrt{7}}{2}.$$ Hence, $$\det(A)=f_n=r_1.s_1^n+r_2.s_2^n,$$ where, using initial conditions $$r_1=\frac{1}{2} +\frac{\iota }{2\sqrt{7}},\ \ r_2=\frac{1}{2} -\frac{\iota }{2\sqrt{7}}.$$ Now, to calculate $A^{-1}$ we need to solve following recursive expressions $$g_i=-g_{i-1}-2g_{i-1}, \ \text{for} \ \ i=2, 3\dots,n,\ \ g_0=1,\ g_1=-1$$ $$ h_i=-h_{i+1}-2h_{i+2}, \ \text{for} \ \ i=n-1,\dots,1, \ \ h_{n+1}=1,\ h_{n}=-1.$$ Similar to $f_n$, solving these recursive expressions we get $$g_i=r_{1}.s_1^i+r_{2}.s_2^i.$$ And, $$h_i=r_{h1}.s_1^{n-i}+r_{h2}.s_2^{n-i},$$ where, $$r_{h1}=\frac{-1}{2}-\frac{3}{2\iota\sqrt(7)},\ \ \ r_{h2}=\frac{-1}{2}+\frac{3}{2\iota\sqrt(7)}.$$ Entries of $A^{-1}$ are clearly given by $g_i, h_i$ (here).

$$A^{-1}_{ij}=\begin{cases}\frac{2^{j-i}g_{i-1}h_{j+1}}{g_n} & \mbox{if $i\le j$} \\ \frac{g_{j-1}h_{i+1}}{g_n} &\mbox{if $j< i$} \end{cases}.$$

$\endgroup$
  • $\begingroup$ I think it is not much different from Amdeberhan's answers. This answer contains a step by step procedure. $\endgroup$ – Dutta Mar 10 '17 at 12:08

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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