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{n2}{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.

$\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
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{nk}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^{ji}f_{i1}f_{nj}+\sum_{j<i}^{1,n}f_{j1}f_{ni} \\ &=f_n+\sum_{i=1}^nf_{i1}f_{ni}+\sum_{j<i}^{1,n}(1+2^{ij})f_{j1}f_{ni}. \end{align}

$\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 nonrecursive 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(n1)2f(n2). $$ $\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
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_{n1}2f_{n2},\ \ \ \ \ 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_{i1}2g_{i1}, \ \text{for} \ \ i=2, 3\dots,n,\ \ g_0=1,\ g_1=1$$ $$ h_i=h_{i+1}2h_{i+2}, \ \text{for} \ \ i=n1,\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^{ni}+r_{h2}.s_2^{ni},$$ 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^{ji}g_{i1}h_{j+1}}{g_n} & \mbox{if $i\le j$} \\ \frac{g_{j1}h_{i+1}}{g_n} &\mbox{if $j< i$} \end{cases}.$$

$\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