MAX DETERMINANT

A SPECIAL MATRIX:

The determinant of $latex M_{n}$, a square matrix with elements $latex m_{i,j}= \max(i,j)$, where $latex \max$ is the maximum function, is given by sequence: A181983

This identity looks as follows:

$latex\displaystyle det{\bigg[ max(i,j) \bigg] }_{1\leq i,j \leq n} = -n \cdot {(-1)}^{n} = A181983(n)$

Proof:

A new matrix with the same determinant can be created, subtracting row i from row i+1 starting at the 2nd row, and then this determinant can be computed easily using the expansion by minors technique at element $latex m_{1,n}$

This can be better shown with an example:

We can transform:

$latex\displaystyle M_{10} = \left(\begin{array}{cccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 2 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 3 & 3 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 4 & 4 & 4 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 5 & 5 & 5 & 5 & 5 & 6 & 7 & 8 & 9 & 10 \\ 6 & 6 & 6 & 6 & 6 & 6 & 7 & 8 & 9 & 10 \\ 7 & 7 & 7 & 7 & 7 & 7 & 7 & 8 & 9 & 10 \\ 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 9 & 10 \\ 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 10 \\ 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 \end{array} \right)$

Into:

$latex\ M^{*}_{10} =\left(\begin{array}{cccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \end{array} \right)$

This proof can be generalized to a very similar kind of matrices, obtaining:

$latex\displaystyle det{\bigg[ max(i,j)^k \bigg]}_{1\leq i,j \leq n} = {(-1)}^{n-1} \cdot n^{k} \cdot \prod_{s=1}^{n-1}{(s+1)^k-s^k}$

$latex\displaystyle det{\bigg[ min(i,j)^k \bigg]}_{1\leq i,j \leq n} = \prod_{s=1}^{n-1}{(s+1)^k-s^k}$

---

References:
[1]- N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. A051125: Table T(n,k) = max{n,k} read by antidiagonals (n >= 1, k >= 1).
[2]- Michael Somos, Apr 04 2012, The On-Line Encyclopedia of Integer Sequences. A181983: -(-1)^n * n.
[3]- Emeric Deutsch, Jun 05 2009, The On-Line Encyclopedia of Integer Sequences. A161124: Number of inversions in all fixed-point-free involutions of {1,2,...,2n}.
[4]- N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. A001147: Double factorial of odd numbers: (2*n-1)!! = 1*3*5*...*(2*n-1).

READER'S CORNER (I)

A BINOMIAL PLAY:

Our contributor Raymond Rogers has sent an alternate proof for:

$latex \displaystyle det{\bigg[ \binom{i+j+k}{i} \bigg]}_{0\leq i,j \leq n} =\binom{n+k+1}{k+1}$

This expression is identical to the one found in the post Binomial Matrix (III), but here the matrices are indexed from zero instead of one.

The proof is entitled A BINOMIAL DETERMINATE,A VERY SHORT PLAY IN THREE ACTS, and it is based on Vandermonde's identity.

Thank you Raymond.

---

Archives:
[a]-120510-Binomial-Play-R.Rogers.pdf

---

Links:
[1]-Raymond Rogers, Lamm´s Equation, Confluent Hypergeometric Equations- Lamm´s Equation Blogspot

---

BINOMIAL MATRIX (III)

If $latex A_n$ is an square matrix with elements:

$latex \displaystyle a_{i,j}=\binom{i+j+k}{i}$

Then:

$latex \displaystyle |A_{n}|=\binom{n+k+1}{k+1}=\binom{n+k+1}{n}$

---

Proof:

The $latex \displaystyle A_{n}$ matrix can be decomposed as the product of a lower triangular matrix, $latex L_{n}$, and an upper triangular matrix, $latex U_{n}$:

$latex \displaystyle A_{n}=L_{n}*U_{n}$

Example:

$latex \displaystyle A_{3}=\left(\begin{array}{ccc} 2+k & 3+k & 4+k \\ \frac{1}{2} (2+k) (3+k) & \frac{1}{2} (3+k) (4+k) & \frac{1}{2} (4+k) (5+k) \\ \frac{1}{6} (2+k) (3+k) (4+k) & \frac{1}{6} (3+k) (4+k) (5+k) & \frac{1}{6} (4+k) (5+k) (6+k) \end{array}\right)$

$latex \displaystyle L_{3}= \left(\begin{array}{ccc} 1 & 0 & 0 \\ \frac{3+k}{2} & 1 & 0 \\ \frac{1}{6} (3+k) (4+k) & \frac{2 (4+k)}{3} & 1 \end{array} \right)$

$latex \displaystyle U_{3}=\left(\begin{array}{ccc} 2+k & 3+k & 4+k \\ 0 & \frac{3+k}{2} & 4+k \\ 0 & 0 & \frac{4+k}{3} \end{array} \right)$

After some trial and error puzzle, we can propose as decomposition:

$latex \displaystyle l_{i,j}=\frac{j}{i} \binom{i+k+1}{j+k+1}$

$latex \displaystyle u_{i,j}=\frac{j+k+1}{j}\binom{j}{i}$

If this decomposition is the correct one then the matrix product should be $latex a_{i,j}$:

$latex \displaystyle \sum_{r=1}^n{l_{i,r} \cdot u_{r,j}=\sum_{r=1}^{min(i,j)}{l_{i,r} \cdot u_{r,j}$

Where:

$latex \displaystyle l_{i,r}=\frac{r}{i} \binom{i+k+1}{r+k+1}$

$latex \displaystyle u_{r,j}=\frac{j+k+1}{j}\binom{j}{r}$

$latex l_{i,r}\cdot u_{r,j}$, can be simplified, changing the binomial coefficient to the gamma function, as:

$latex \displaystyle l_{i,r} \cdot u_{r,j}=\frac{j+k+1}{i}\binom{j-1}{r-1}\binom{i+k+1}{r+k+1}$

$latex \displaystyle \sum_{r=1}^{min(i,j)}{l_{i,r} \cdot u_{r,j}=\sum_{r=1}^{min(i,j)}{\frac{j+k+1}{i}\binom{j-1}{r-1}\binom{i+k+1}{r+k+1}} = $

$latex \displaystyle = \frac{j+k+1}{i} \cdot \sum_{r=1}^{min(i,j)}{\binom{j-1}{r-1}\binom{i+k+1}{r+k+1}} = \frac{j+k+1}{i} \cdot \binom{i+j+k}{j+k+1}=$

$latex \displaystyle=\frac{i}{i}\cdot \binom{i+j+k}{j+k}=\binom{i+j+k}{i}=a_{i,j}$

In the last part of the proof, involving binomial coefficients, we have used: (See ref [1] and [2])

1) $latex \displaystyle \sum_{r}^{}{\binom{l}{r+m} \binom{s}{r+n}}=\binom{l+s}{l-m+n}$

2) $latex \displaystyle r\binom{i}{r}=i \binom{i-1}{r-1}$


Now we can calculate easily $latex |A_n|$, because the LU-decomposition used is the so called Doolittle decomposition, where the matrix $latex L_{n}$ has all ones on its diagonal.

$latex \displaystyle |A_{n}|=\prod_{i=1}^{n}{l_{i,i} \cdot u_{i,i}}=\prod_{i=1}^{n}{u_{i,i}}=\prod_{i=1}^{n}{\frac{i+k+1}{i}}=\binom{n+k+1}{n}$

---

Archives:
[a]-092609-Binomial Matrix (III).nb

---

References:
[1]-Ronald L. Graham, Donald E. Knuth, and Oren Patashnik (Reading, Massachusetts: Addison-Wesley, 1994 - Concrete Mathematics - Identity (5.32) in Table 169.
[2]-Matthew Hubbard and Tom Roby - Pascal's Triangle From Top To Bottom - the binomial coefficient website- Catalog #: 3100004.

---

BINOMIAL MATRIX (II)

If $latex A_n$ is an square matrix with elements:

$latex \displaystyle a_{i,j}=\binom{i+k}{j}$

Then:

$latex \displaystyle |A_{n}|=\binom{n+k}{n}$

---

Proof:

The $latex \displaystyle A_{n}$ matrix can be decomposed as the product of a lower triangular matrix, $latex \displaystyle L_{n}$, and an upper triangular matrix, $latex \displaystyle U_{n}$:

$latex \displaystyle A_{n}=L_{n}*U_{n}$

Example:

$latex \displaystyle A_{3}=\left(\begin{array}{ccc} 1+k & \frac{1}{2} k (1+k) & \frac{1}{6} (-1+k) k (1+k) \\ 2+k & \frac{1}{2} (1+k) (2+k) & \frac{1}{6} k (1+k) (2+k) \\ 3+k & \frac{1}{2} (2+k) (3+k) & \frac{1}{6} (1+k) (2+k) (3+k) \end{array} \right)$

$latex \displaystyle L_{3}=\left(\begin{array}{ccc} 1 & 0 & 0 \\ \frac{2+k}{1+k} & 1 & 0 \\ \frac{3+k}{1+k} & \frac{2 (3+k)}{2+k} & 1 \end{array} \right)$

$latex \displaystyle U_{3}=\left( \begin{array}{ccc} 1+k & \frac{1}{2} k (1+k) & \frac{1}{6} (-1+k) k (1+k) \\ 0 & \frac{2+k}{2} & \frac{1}{3} k (2+k) \\ 0 & 0 & \frac{3+k}{3}\end{array} \right)$

After some math "plumbing", we can propose as decomposition:

$latex \displaystyle l_{i,j}=\frac{i + k}{j + k} \binom{i - 1}{j - 1}$

$latex \displaystyle u_{i,j}=\binom{j - 1}{i - 1} \binom{i + k}{j} {\binom{k + i - 1}{i - 1}}^{-1}$

If this decomposition is correct then the matrix product should be $latex \displaystyle a_{i,j}$:

$latex \displaystyle \sum_{r=1}^n{l_{i,r} \cdot u_{r,j}}=\sum_{r=1}^{min(i,j)}{l_{i,r} \cdot u_{r,j}}$

Where:

$latex \displaystyle l_{i,r}=\frac{i + k}{r + k} \binom{i - 1}{r - 1}$

$latex \displaystyle u_{r,j}=\binom{j - 1}{r - 1} \binom{r + k}{j} {\binom{k + r - 1}{r - 1}}^{-1}$

$latex \displaystyle l_{i,r} \cdot u_{r,j}$, can be simplified, changing the binomial coefficient to the gamma function, as:

$latex \displaystyle l_{i,r} \cdot u_{r,j}=\frac{(i+k)\cdot r}{i \cdot j}\cdot\binom{i}{r}\binom{k}{j-r}$

$latex \displaystyle \sum_{r=1}^{min(i,j)}{l_{i,r} \cdot u_{r,j}}=\sum_{r=1}^{min(i,j)}{\frac{(i+k) r}{i \cdot j}\cdot\binom{i}{r}\binom{k}{j-r}}=\\ \frac{(i+k)}{i \cdot j} \cdot \sum_{r=1}^{min(i,j)}{r\binom{i}{r}\binom{k}{j-r}}$

This last expression can be simplified, with the help of:

$latex \displaystyle r\binom{i}{r}=i \binom{i-1}{r-1}$, the Vandermonde´s convolution (see reference [2]), and the absortion formula (see reference [3]), to:

$latex \displaystyle \sum_{r=1}^{min(i,j)}{l_{i,r} \cdot u_{r,j}}=\binom{i+k}{j}=a_{i,j}$

Now we can calculate easily $latex |A_n|$, because the LU-decomposition used is the so called Doolittle decomposition, where the matrix $latex L_{n}$ has all ones on its diagonal.

$latex \displaystyle |A_{n}|=\prod_{i=1}^{n}{l_{i,i}*u_{i,i}}=\prod_{i=1}^{n}{u_{i,i}}=\prod_{i=1}^{n}{\frac{i+k}{i}}=\binom{n+k}{k}=\binom{n+k}{n}$

---

Archives:[a]-092609-Binomial Matrix (II).nb

---

References:

[1]-John H. Mathews and Kurtis Fink, 2004 - Module for PA = LU Factorization with Pivoting
[2]-Matthew Hubbard and Tom Roby - Pascal's Triangle From Top To Bottom - the binomial coefficient website- Catalog #: 3100003.
[3]-Matthew Hubbard and Tom Roby - Pascal's Triangle From Top To Bottom - the binomial coefficient website- Catalog #: 2400002.

---

BINOMIAL MATRIX (I)

If we use yesterday's idea, with little variations, we can create new expressions for matrices with elements related to binomial coefficients, for instance:

Let be $latex U_n$ an square matrix with elements:

$latex \displaystyle u_{i,j}=\binom{j}{i}$

$latex U_n$ is an upper triangular matrix with all its diagonal elements equal to $latex 1$, and similar to Pascal's triangle.(That I prefer to name Tartaglia's Triangle)

Example:

$latex U_{10}= \left( \begin{array}{cccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 0 & 1 & 3 & 6 & 10 & 15 & 21 & 28 & 36 & 45\\ 0 & 0 & 1 & 4 & 10 & 20 & 35 & 56 & 84 & 120 \\ 0 & 0 & 0 & 1 & 5 & 15 & 35 & 70 & 126 & 210 \\ 0 & 0 & 0 & 0 & 1 & 6 & 21 & 56 & 126 & 252 \\ 0 & 0 & 0 & 0 & 0 & 1 & 7 & 28 & 84 & 210 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 8 & 36 & 120 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 9 & 45 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 10 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{array} \right)$

And, of course:

$latex |U_{n}|=1$

If we multiply this matrix by its transposed one, then we get a symmetrical matrix with:

$latex |A_{n}|=|U_{n}^{T}*U_{n}|=|U_{n}|^2=1$

Example:

$latex A_{10}=U_{10}^{T}*U_{10}$

$latex \displaystyle A_{10}=\\ \\ \left( \begin{array}{cccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 2 & 5 & 9 & 14 & 20 & 27 & 35 & 44 & 54 & 65 \\ 3 & 9 & 19 & 34 & 55 & 83 & 119 & 164 & 219 & 285 \\ 4 & 14 & 34 & 69 & 125 & 209 & 329 & 494 & 714 & 1000 \\ 5 & 20 & 55 & 125 & 251 & 461 & 791 & 1286 & 2001 & 3002 \\ 6 & 27 & 83 & 209 & 461 & 923 & 1715 & 3002 & 5004 & 8007 \\ 7 & 35 & 119 & 329 & 791 & 1715 & 3431 & 6434 & 11439 & 19447 \\ 8 & 44 & 164 & 494 & 1286 & 3002 & 6434 & 12869 & 24309 & 43757 \\ 9 & 54 & 219 & 714 & 2001 & 5004 & 11439 & 24309 & 48619 & 92377 \\ 10 & 65 & 285 & 1000 & 3002 & 8007 & 19447 & 43757 & 92377 & 184755 \end{array}\right)$

So we have constructed a new matrix with determinant equal to one:

$latex \displaystyle a_{i,j}=\sum_{r=1}^n{u_{i,r}^{*} \cdot u_{r,j}}=\sum_{r=1}^{min(i,j)}{u_{r,i} \cdot u_{r,j}}$

$latex \displaystyle a_{i,j}=\sum_{r=1}^{min(i,j)}{\binom{i}{r} \binom{j}{r}}=-1+\sum_{r=0}^{i}{\binom{i}{r} \binom{j}{r}}=\binom{i+j}{i}-1=\binom{i+j}{j}-1$

Note(i): For a proof on binomial identity see references [1] or [2]

---

OEIS Related Sequences:

Row/Column	Sequence
1	A000027
2	A000096
3	A062748
4	A063258
5	A062988
6	A124089
7	A124090
8	A165618
9	A035927
10	-

---

References:
[1]-Ronald L. Graham, Donald E. Knuth, and Oren Patashnik (Reading, Massachusetts: Addison-Wesley, 1994 - Concrete Mathematics - Identity (5.32) in Table 169.
[2]-Matthew Hubbard and Tom Roby - Pascal's Triangle From Top To Bottom - the binomial coefficient website- Catalog #: 3100004.

---

BETA FUNCTION MATRIX DETERMINANT

If $latex A_n$ is an square matrix of order $latex n$, whose elements are defined as:

$latex \displaystyle a_{i,j}=\frac{1}{\beta(i,j)}$, where $latex \beta$ is the beta function. Then:

$latex |A_{n}|=n!$

---

Proof:

If we use Cholesky method, we can decompose this matrix as:

$latex A_{n}=U_{n}^{T}*U_n$

Where $latex U_n$ is an upper triangular matrix.

But instead of applying the algorithm to a generic case, we are going to propose a factorization, and after we will check that this decomposition generates the appropriate matrix. This mean to use software to speed up the proof, like:

$latex \displaystyle A_{5}=\left(\begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 2 & 6 & 12 & 20 & 30 \\ 3 & 12 & 30 & 60 & 105 \\ 4 & 20 & 60 & 140 & 280 \\ 5 & 30 & 105 & 280 & 630 \end{array} \right)= U_{n}^{T}* \left( \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 0 & \sqrt{2} & 3 \sqrt{2} & 6 \sqrt{2} & 10 \sqrt{2} \\ 0 & 0 & \sqrt{3} & 4 \sqrt{3} & 10 \sqrt{3} \\ 0 & 0 & 0 & 2 & 10 \\ 0 & 0 & 0 & 0 & \sqrt{5} \end{array} \right)$

The elements of $latex U_n$, seems to be:

$latex \displaystyle u_{i,j}=\sqrt{i}\cdot \binom{j}{i}$

$latex U_{n}^T$ is the transpose of $latex U_n$, so:

$latex \displaystyle u_{i,j}^{*}=u_{j,i}=\sqrt{j} \cdot \binom{i}{j}$

If we multiply both triangular matrices:

$latex \displaystyle a_{i,j}=\sum_{r=1}^n{u_{i,r}^{*} \cdot u_{r,j}} =\sum_{r=1}^n{r \cdot \binom{i}{r} \binom{j}{r}}=\sum_{r=1}^{min(i,j)}{r \cdot \binom{i}{r} \binom{j}{r}}$

This last binomial expression, can be added to a closed form, equal to the reciprocal of beta function, (See proof on reference [1])

$latex \displaystyle a_{i,j}=i \cdot \binom{i+j-1}{j-1}=\frac{1}{\beta(i,j)}$

Now, that we have found this decomposition, for $latex A_n$, then it is unique and $latex A_n$ is Hermitian and positive definite.

$latex \displaystyle |A_{n}|=|U_{n}^{T}*U_{n}|=|U_{n}|^{2}=\left(\prod_{i=1}^{n}{u_{i,i}}\right)^{2}=\prod_{i=1}^{n}{u_{i,i}^2}=\prod_{i=1}^{n}{\left(\sqrt{i}\cdot\binom{i}{i}\right)^2}=\prod_{i=1}^{n}{i}=n!$

---

Archives:[a]-092109-Beta Determinant.nb

---

References:
[1]-Ronald L. Graham, Donald E. Knuth, and Oren Patashnik (Reading, Massachusetts: Addison-Wesley, 1994 - Concrete Mathematics - page 181 Problem 5
[2]-A000142-Factorial numbers: n! The On-Line Encyclopedia of Integer Sequences!

---