12
$\begingroup$

Let $A_{n}$ be the $(n+1) \times(n+1)$ matrix with coefficients $$ a_{i j}={i+j \choose i} $$ (binomial coefficients), where the rows and columns are indexed by the numbers from 0 to $n$ are indexed.

Now I want to determine the Determinant and with the first 5 matrices i found out that it is $n+1$ if i did not make a mistake. The Matrix looks like this: $$ \left(\begin{matrix} {1+1 \choose 1} & {1+2 \choose 1} & {1+3 \choose 1} & \dots & {1+n+1 \choose 1} \\ {2+1 \choose 2} & {2+2 \choose 2} & {2+3 \choose 2} & \dots & {2+n+1 \choose 2} \\ {3+1 \choose 3} &{3+2 \choose 3} & {3+3 \choose 3} & \dots & {3+n+1 \choose 3} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {n+1+1 \choose n+1} & {n+1+2 \choose n+1} & {n+1+3 \choose n+1} & \dots & {n+1+n+1 \choose n+1} \end{matrix}\right) $$ The Problem is to bring this Matrix into an upper or lower triangle matrix. If anyone has hints or ideas that can help, please help, thanks in advance. Maybe the approach is not even good. If I make progress at all i will update this question.

$\endgroup$
1
  • 1
    $\begingroup$ Are the rows and columns indexed $0$ through $n$ as in your description, or $1$ through $n+1$ as in your matrix? $\endgroup$ Aug 6, 2021 at 19:40

4 Answers 4

1
$\begingroup$

Answer : $n+1$

Explanation : It can be compute by using Pascal triangle formula ${n+1 \choose k+1} = {n \choose k} + {n \choose k+1}$.

First the determinant is the same by transforming each columns from $n+1$ to $2$ by it value minus the value of the previous column ($C_n$ become $C_n-C_{n-1}$). As ${n+1 \choose k+1}-{n \choose k+1} = {n \choose k}$ then

$$\begin{vmatrix} {1+1 \choose 1} & {1+2 \choose 1} & {1+3 \choose 1} & \dots & {1+n+1 \choose 1} \\ {2+1 \choose 2} & {2+2 \choose 2} & {2+3 \choose 2} & \dots & {2+n+1 \choose 2} \\ {3+1 \choose 3} &{3+2 \choose 3} & {3+3 \choose 3} & \dots & {3+n+1 \choose 3} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {n+1+1 \choose n+1} & {n+1+2 \choose n+1} & {n+1+3 \choose n+1} & \dots & {n+1+n+1 \choose n+1} \end{vmatrix} = \begin{vmatrix} {1+1 \choose 1} & {1+1 \choose 0} & {1+2 \choose 0} & \dots & {1+n \choose 0} \\ {2+1 \choose 2} & {2+1 \choose 1} & {2+2 \choose 1} & \dots & {2+n \choose 1} \\ {3+1 \choose 3} &{3+1 \choose 2} & {3+2 \choose 2} & \dots & {3+n \choose 2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {n+1+1 \choose n+1} & {n+1+1 \choose n} & {n+1+2 \choose n} & \dots & {n+1+n \choose n} \end{vmatrix} = \begin{vmatrix} {1+1 \choose 1} & 1 & 1 & \dots & 1 \\ {2+1 \choose 2} & {2+1 \choose 1} & {2+2 \choose 1} & \dots & {2+n \choose 1} \\ {3+1 \choose 3} &{3+1 \choose 2} & {3+2 \choose 2} & \dots & {3+n \choose 2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {n+1+1 \choose n+1} & {n+1+1 \choose n} & {n+1+2 \choose n} & \dots & {n+1+n \choose n} \end{vmatrix}$$

Second the determinant is the same by transforming each rows from $n+1$ to $2$ by it value minus the value of the previous row ($L_n$ become $L_n-L_{n-1}$). As ${n+1 \choose k+1}-{n \choose k} = {n \choose k+1}$ then $$\begin{vmatrix} {1+1 \choose 1} & 1 & 1 & \dots & 1 \\ {2+1 \choose 2} & {2+1 \choose 1} & {2+2 \choose 1} & \dots & {2+n \choose 1} \\ {3+1 \choose 3} &{3+1 \choose 2} & {3+2 \choose 2} & \dots & {3+n \choose 2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {n+1+1 \choose n+1} & {n+1+1 \choose n} & {n+1+2 \choose n} & \dots & {n+1+n \choose n} \end{vmatrix} = \begin{vmatrix} {1+1 \choose 1} & 1 & 1 & \dots & 1 \\ {2 \choose 2} & {1+1 \choose 1} & {1+2 \choose 1} & \dots & {1+n \choose 1} \\ {3 \choose 3} &{2+1 \choose 2} & {2+2 \choose 2} & \dots & {2+n \choose 2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {n+1 \choose n+1} & {n+1 \choose n} & {n+2 \choose n} & \dots & {n+n \choose n} \end{vmatrix} = \begin{vmatrix} 2 & 1 & 1 & \dots & 1 \\ 1 & {1+1 \choose 1} & {1+2 \choose 1} & \dots & {1+n \choose 1} \\ 1 &{2+1 \choose 2} & {2+2 \choose 2} & \dots & {2+n \choose 2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & {n+1 \choose n} & {n+2 \choose n} & \dots & {n+n \choose n} \end{vmatrix}$$

We can remark than this matrix from row $2$ to $n+1$ (and column $2$ to $n+1$) is the lower matrix of our initial matrix. So by doing the same two operations as above from row (and column) $3$ to $n+1$, I will get $$\begin{vmatrix} 2 & 1 & 0 & \dots & 0 \\ 1 & 2 & 1 & \dots & 1 \\ 0 & 1 & {1+1 \choose 1} & \dots & {1+(n-1) \choose 1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 1 & {(n-1)+1 \choose n-1} & \dots & {(n-1)+(n-1) \choose n-1} \end{vmatrix}$$. I do the same two operation several time and then get $$\begin{vmatrix} 2 & 1 & 0 & \dots & 0 \\ 1 & 2 & 1 & \dots & 1 \\ 0 & 1 & 2 & \dots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \dots & 2 \end{vmatrix}$$. It is the matrix with $2$ on the principal diagonal and $1$ on the $2$ secondary diagonals. This determinant can be determine by setting $$I_{n+1} = \begin{vmatrix} 2 & 1 & 0 & \dots & 0 \\ 1 & 2 & 1 & \dots & 1 \\ 0 & 1 & 2 & \dots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \dots & 2 \end{vmatrix} = 2I_n-I_{n-1}$$ with $I_0=1$ and $I_1=1$. This recurrent equation give $I_n = n+1$.

$\endgroup$
0
$\begingroup$

Let's consider the version where the columns are indexed from $0$ to $n$. Consider for example

$$ A_3 = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 2 & 3 & 4 \\ 1 & 3 & 6 & 10 \\ 1 & 4 & 10 & 20 \end{bmatrix}. $$

Note that each element in the matrix (except the elements in the $0$th row and column) is the sum of the element above it and the element to the left of it. This is the "Pascal Triangle" property of the matrix.

How can we reduce $A_4$ to an upper triangular matrix? By the Pascal Triangle property, if we replace row $R_i$ by $R_i - R_{i-1}$, the resulting row is just $R_i$, shifted to the right (with the first element padded by zero and the last element dropped). So for example, $$ \begin{bmatrix} 1 & 1 & 1 & 1 \\ \color{pink}{1} & \color{\pink}{2} & \color{\pink}{3} & 4 \\ \color{red}{1} & \color{red}{3} & \color{red}{6} & 10 \\ \color{blue}{1} & \color{blue}{4} & \color{blue}{10} & 20 \end{bmatrix} \xrightarrow{R_4 = R_4 - R_3} \begin{bmatrix} 1 & 1 & 1 & 1 \\ \color{pink}{1} & \color{pink}{2} & \color{pink}{3} & 4 \\ \color{red}{1} & \color{red}{3} & \color{red}{6} & 10 \\ 0 & \color{blue}{1} & \color{blue}{4} & \color{blue}{10} \end{bmatrix} \xrightarrow{R_3 = R_3 - R_2} \begin{bmatrix} 1 & 1 & 1 & 1 \\ \color{pink}{1} & \color{pink}{2} & \color{pink}{3} & 4 \\ 0 & \color{red}{1} & \color{red}{3} & \color{red}{6} \\ 0 & \color{blue}{1} & \color{blue}{4} & \color{blue}{10} \end{bmatrix} \xrightarrow{R_2 = R_2 - R_1} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 0 & \color{pink}{1} & \color{pink}{2} & \color{pink}{3} \\ 0 & \color{red}{1} & \color{red}{3} & \color{red}{6} \\ 0 & \color{blue}{1} & \color{blue}{4} & \color{blue}{10} \end{bmatrix}. $$

Now the corner $3 \times 3$ matrix again satisfies the "Pascal Triangle" property so you can repeat this process and get $$ \begin{bmatrix} 1 & 1 & 1 & 1 \\ 0 & \color{pink}{1} & \color{pink}{2} & \color{pink}{3} \\ 0 & \color{red}{1} & \color{red}{3} & \color{red}{6} \\ 0 & \color{blue}{1} & \color{blue}{4} & \color{blue}{10} \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 1 & 1 & 1 \\ 0 & \color{pink}{1} & \color{pink}{2} & \color{pink}{3} \\ 0 & 0 & \color{red}{1} & \color{red}{3} \\ 0 & 0 & \color{blue}{1} & \color{blue}{4} \end{bmatrix}. $$

Repeating this process once again for the corner $2 \times 2$ matrix, we get $$ \begin{bmatrix} 1 & 1 & 1 & 1 \\ 0 & \color{pink}{1} & \color{pink}{2} & \color{pink}{3} \\ 0 & 0 & \color{red}{1} & \color{red}{3} \\ 0 & 0 & \color{blue}{1} & \color{blue}{4} \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 1 & 1 & 1 \\ 0 & \color{pink}{1} & \color{pink}{2} & \color{pink}{3} \\ 0 & 0 & \color{red}{1} & \color{red}{3} \\ 0 & 0 & 0 & \color{blue}{1} \end{bmatrix} $$ which is an upper triangular matrix with $1$'s on the diagonal so the determinant of the matrix is one.

I'll leave you the details of generalizing this argument to the $(n+1)\times(n+1)$ case and how one can use it to calculate the shifted determinant.

$\endgroup$
2
  • 1
    $\begingroup$ This does not seem to be the determinant of the matrix he proposed even for $n=3$ $\endgroup$ Aug 7, 2021 at 3:37
  • $\begingroup$ @AbdoulHaki: In the question, the OP asked for the determinant of the matrix where the rows and columns are indexed by $0,\dots,n$ but wrote the submatrix with indices $1,\dots,n$. Like I wrote in the beginning of my answer, I answered the version with indices $0,\dots,n$... $\endgroup$
    – levap
    Aug 8, 2021 at 10:55
0
$\begingroup$

Let $L_n$ be an $n\times n$ matrix with $1$'s on the diagonal and $-1$'s on the subdiagonal. $L_nM$ is $M$ with row $i-1$ subtracted from row $i$, for $2\le i\le n$.

Let $R_n$ be an $n\times n$ matrix with $1$'s on the diagonal and $-1$'s on the superdiagonal. $MR_n$ is $M$ with column $j-1$ subtracted from column $j$, for $2\le j\le n$.

Being lower and upper triangular matrices with $1$'s on the diagonal, we have $\det(L_n)=\det(R_n)=1$.


A Simpler Matrix

Let $U_n$ be an $n\times n$ matrix with elements $$ U_{n,i,j}=\left[\binom{i+j-2}{i-1}\right]_{i,j=1}^n\tag1 $$ For example, $$ U_5= \begin{bmatrix} 1 & 1 & 1 & 1 & 1 \\ 1 & 2 & 3 & 4 & 5 \\ 1 & 3 & 6 & 10 & 15 \\ 1 & 4 & 10 & 20 & 35 \\ 1 & 5 & 15 & 35 & 70 \\ \end{bmatrix}\tag2 $$ Using Pascal's Identity, we see that $L_nU_nR_n$ has a $1$ in the upper left and $0$'s in the remainder if the top row and left column. The lower-right $n-1\times n-1$ submatrix is $U_{n-1}$. For example, subtracting each row from the next (bottom to top) gives $$ L_5U_5= \begin{bmatrix} 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 3 & 4 \\ 0 & 1 & 3 & 6 & 10 \\ 0 & 1 & 4 & 10 & 20 \\ 0 & 1 & 5 & 15 & 35 \\ \end{bmatrix}\tag3 $$ then subtracting each column from the next (right to left) gives $$ L_5U_5R_5= \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 3 & 4 \\ 0 & 1 & 3 & 6 & 10 \\ 0 & 1 & 4 & 10 & 20 \\ \end{bmatrix}\tag4 $$ Extending $(2)$ and $(4)$ shows that $$ \begin{align} \det(U_n) &=\det(L_nU_nR_n)\tag{5a}\\[6pt] &=\det(U_{n-1})\tag{5b}\\[6pt] &=1\tag{5c} \end{align} $$ Explanation:
$\text{(5a)}$: $\det(L_n)=\det(R_n)=1$
$\text{(5b)}$: expand the determinant on the first column
$\text{(5c)}$: induction and $\det(U_1)=1$


The Matrix of Interest

Let $T_n$ be an $n\times n$ matrix with elements $$ T_{n,i,j}=\left[\binom{i+j}{i}\right]_{i,j=1}^n\tag6 $$ For example, $$ T_5= \begin{bmatrix} 2 & 3 & 4 & 5 & 6 \\ 3 & 6 & 10 & 15 & 21 \\ 4 & 10 & 20 & 35 & 56 \\ 5 & 15 & 35 & 70 & 126 \\ 6 & 21 & 56 & 126 & 252 \\ \end{bmatrix}\tag7 $$ Using Pascal's Identity, we see that $L_nT_nR_n$ has a $2$ in the upper left and the rest of the matrix is $U_n$. For example, subtracting each row from the next (bottom to top) gives $$ L_5T_5= \begin{bmatrix} 2 & 3 & 4 & 5 & 6 \\ 1 & 3 & 6 & 10 & 15 \\ 1 & 4 & 10 & 20 & 35 \\ 1 & 5 & 15 & 35 & 70 \\ 1 & 6 & 21 & 56 & 126 \\ \end{bmatrix}\tag8 $$ then subtracting each column from the next (right to left) gives $$ L_5T_5R_5= \begin{bmatrix} 2 & 1 & 1 & 1 & 1 \\ 1 & 2 & 3 & 4 & 5 \\ 1 & 3 & 6 & 10 & 15 \\ 1 & 4 & 10 & 20 & 35 \\ 1 & 5 & 15 & 35 & 70 \\ \end{bmatrix}\tag9 $$ Extending $(7)$ and $(9)$ shows that $$ \begin{align} \det(T_n) &=\det(L_nT_nR_n)\tag{10a}\\[6pt] &=\det(T_{n-1})+\det(U_n)\tag{10b}\\[6pt] &=\det(T_{n-1})+1\tag{10c}\\[6pt] &=n+1\tag{10d} \end{align} $$ Explanation:
$\text{(10a)}$: $\det(L_n)=\det(R_n)=1$
$\text{(10b)}$: expand the determinant on the first column
$\text{(10c)}$: $\det(U_n)=1$
$\text{(10d)}$: induction and $\det(T_1)=2$

$\endgroup$
-1
$\begingroup$

Expressing the combinatorial coefficient in factorials, then taking out all the common factors, we have \begin{align*} & \begin{vmatrix} \binom{1 + 1}{1} & \binom{1 + 2}{1} & \binom{1 + 3}{1} & \cdots & \binom{1 + n + 1}{1} \\ \binom{2 + 1}{2} & \binom{2 + 2}{2} & \binom{2 + 3}{2} & \cdots & \binom{2 + n + 1}{2} \\ \binom{3 + 1}{3} & \binom{3 + 2}{3} & \binom{3 + 3}{3} & \cdots & \binom{3 + n + 1}{3} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \binom{n + 1 + 1}{n + 1} & \binom{n + 1 + 2}{n + 1} & \binom{n + 1 + 3}{n + 1} & \cdots & \binom{n + 1 + n + 1}{n + 1} \\ \end{vmatrix} \\ = & \begin{vmatrix} \frac{2!}{1!1!} & \frac{3!}{1!2!} & \frac{4!}{1!3!} & \cdots & \frac{(n + 2)!}{1!(n + 1)!} \\ \frac{3!}{2!1!} & \frac{4!}{2!2!} & \frac{5!}{2!3!} & \cdots & \frac{(n + 3)!}{2!(n + 1)!}\\ \frac{4!}{3!1!} & \frac{5!}{3!2!} & \frac{6!}{3!3!} & \cdots & \frac{(n + 4)!}{3!(n + 1)!} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \frac{(n + 2)!}{(n + 1)!1!} & \frac{(n + 3)!}{(n + 1)!2!} & \frac{(n + 4)!}{(n + 1)!3!} & \cdots & \frac{(2n + 2)!}{(n + 1)!(n + 1)!} \end{vmatrix} \\ =& \left(\frac{1}{1!2!3!\cdots (n + 1)!}\right)^2\times 2!3!4!\cdots(n+2)! \begin{vmatrix} 1 & 3 & 4 \times 3 & \cdots & \prod_{j = 3}^{n + 2}j \\ 1 & 4 & 5 \times 4 & \cdots & \prod_{j = 4}^{n + 3}j \\ 1 & 5 & 6 \times 5 & \cdots & \prod_{j = 5}^{n + 4}j \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & n + 3 & (n + 4)(n + 3) & \cdots & \prod_{j = n + 3}^{2n + 2}j \end{vmatrix} \\ =& \frac{(n + 2)!}{1!2!3!\cdots (n + 1)!} \begin{vmatrix} 1 & 3 & \prod_{j = 0}^1 (4 - j) & \cdots & \prod_{j = 0}^{n - 1}(n + 2 - j) \\ 1 & 4 & \prod_{j = 0}^1 (5 - j) & \cdots & \prod_{j = 0}^{n - 1}(n + 3 - j) \\ 1 & 5 & \prod_{j = 0}^1 (6 - j) & \cdots & \prod_{j = 0}^{n - 1}(n + 4 - j) \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & n + 3 & \prod_{j = 0}^1(n + 4 - j) & \cdots & \prod_{j = 0}^{n - 1}(2n + 2 - j) \end{vmatrix} \\ =& \frac{(n + 2)!}{1!2!3!\cdots (n + 1)!} \begin{vmatrix} 1 & (n + 2) - (n - 1) & \prod\limits_{j = n - 2}^{n - 1} (n + 2 - j) & \cdots & \prod\limits_{j = 0}^{n - 1}(n + 2 - j) \\ 1 & (n + 3) - (n - 1) & \prod\limits_{j = n - 2}^{n - 1} (n + 3 - j) & \cdots & \prod\limits_{j = 0}^{n - 1}(n + 3 - j) \\ 1 & (n + 4) - (n - 1) & \prod\limits_{j = n - 2}^{n - 1} (n + 4 - j) & \cdots & \prod\limits_{j = 0}^{n - 1}(n + 4 - j) \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & (2n + 2) - (n - 1) & \prod\limits_{j = n - 2}^{n - 1} (2n + 2 - j) & \cdots & \prod\limits_{j = 0}^{n - 1}(2n + 2 - j) \end{vmatrix} \\ =& \frac{(n + 2)!}{1!2!3!\cdots (n + 1)!} \begin{vmatrix} \phi_0(n + 2) & \phi_1(n + 2) & \phi_2(n + 2) & \cdots & \phi_{n}(n + 2)\\ \phi_0(n + 3) & \phi_1(n + 3) & \phi_2(n + 3) & \cdots & \phi_{n}(n + 3)\\ \phi_0(n + 4) & \phi_1(n + 4) & \phi_2(n + 4) & \cdots & \phi_{n}(n + 4)\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \phi_0(2n + 2) & \phi_1(2n + 2) & \phi_2(2n + 2) & \cdots & \phi_{n}(2n + 2) \end{vmatrix} \\ =& \frac{(n + 2)!}{1!2!3!\cdots (n + 1)!} \times \prod_{n + 2 \leq i < j \leq 2n + 2}(j - i), \end{align*} where $\phi_0(x) \equiv 1$, $\phi_k(x) = (x - (n - 1))(x - (n - 2))\cdots(x - (n - k)), k = 1, \ldots, n - 1$ is an order-$k$ polynomial. In the last equality, we used the result: for any order-$k$ polynomial $\phi_k(x), k = 0, 1, \ldots, n$, \begin{align*} \begin{vmatrix} \phi_0(x_1) & \phi_1(x_1) & \phi_2(x_1) & \cdots & \phi_{n}(x_1)\\ \phi_0(x_2) & \phi_1(x_2) & \phi_2(x_2) & \cdots & \phi_{n}(x_2)\\ \phi_0(x_3) & \phi_1(x_3) & \phi_2(x_3) & \cdots & \phi_{n}(x_3)\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \phi_0(x_{n + 1}) & \phi_1(x_{n + 1}) & \phi_2(x_{n + 1}) & \cdots & \phi_{n}(x_{n + 1}) \end{vmatrix} = a_0a_1\cdots a_n\prod_{1 \leq i < j \leq n + 1}(x_j - x_i), \end{align*} where $a_k$ is the coefficient of the term $x^k, k = 0, 1, \ldots, n$. This result can be proven by using the Cauchy-Binet formula and Vandermonde determinant.

$\endgroup$
2
  • $\begingroup$ I wonder how long typing up these determinants took ... $\endgroup$
    – L. F.
    Aug 7, 2021 at 2:10
  • 1
    $\begingroup$ The result can be simpler. See my proposition below. $\endgroup$ Aug 7, 2021 at 3:39

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.