Determinants of matrices defined by the minimum/maximum indices of their entries

$ \newcommand{\m}[1]{\left( \begin{matrix} #1 \end{matrix} \right)} $ The Problem: Consider the matrices $A_n := \left(a^{(n)}_{i,j}\right)_{1 \le i,j \le n},B_n := \left(b^{(n)}_{i,j}\right)_{1 \le i,j \le n} \in M_{n \times n}(\Bbb R)$ with entries defined as follows:

$$a^{(n)}_{i,j} := \min \{i,j\} \qquad b^{(n)}_{i,j} := \max \{i,j\}$$

(Examples of these matrices follow momentarily, to show how the structure of each "evolves" and emerges as $n$ increases.)

What are $\det(A_n)$ and $\det(B_n)$ in the general $n \times n$ case, for each $n \in \Bbb Z^+$?

Background/Context: I happened to have a question similar to this on my linear algebra final a few weeks ago. (In full disclosure: final grades have already been determined and all that, so this isn't any longer an "active" test question.) However, that problem used a matrix similar to $A_n$, without specific numbers, and only the $4 \times 4$ case.

I then recently found a video by Dr. Peyam which considered the $5 \times 5$ cases for both $A_n$ and $B_n$, and hinted that these possibly came from a Putnam exam. I'm not sure if it was, though. I looked back through all of the Putnam problems back to $1985$ and didn't see this exact one, though one was similar: $A2$ from $2014$, where $A_n$ is instead defined by $a^{(n)}_{i,j} = 1/\min\{i,j\}$. (Maybe I'll look at that some other time.)

I imagine the definition for $B_n$ is just considered a natural generalization of this problem. In any event, I couldn't find this problem handled in its generality on MSE, so I figured I'd try to figure it out, and post my own solution.

Of course, if you have your own solutions, they're greatly welcomed! Each can provide their own insights.

Small Cases for the Matrices: To help show the structure of the matrices, $A_n$ and $B_n$ look like, in the cases for $n=1,2,\cdots,6$, as follows. Determinants are included, but calculated by Wolfram.

\begin{alignat*}{3} &\boxed{n=1} &&\qquad A_1 = \m{ 1 } &&\qquad \det(A_1) = 1\\ & &&\qquad B_1 = \m{ 1 } &&\qquad \det(B_1) = 1\\ &\boxed{n=2} &&\qquad A_2 = \m{ 1 & 1 \\ 1 & 2 } &&\qquad \det(A_2) = 1\\ & &&\qquad B_2 = \m{ 1 & 2 \\ 2 & 2 } &&\qquad \det(B_2) = -2\\ &\boxed{n=3} &&\qquad A_3 = \m{ 1 & 1 & 1 \\ 1 & 2 & 2 \\ 1 & 2 & 3 } &&\qquad \det(A_3) = 1\\ & &&\qquad B_3 = \m{ 1 & 2 & 3 \\ 2 & 2 & 3 \\ 3 & 3 & 3 } &&\qquad \det(B_3) = 3\\ &\boxed{n=4} &&\qquad A_4 = \m{ 1 & 1 & 1 & 1 \\ 1 & 2 & 2 & 2 \\ 1 & 2 & 3 & 3 \\ 1 & 2 & 3 & 4 } &&\qquad \det(A_4) = 1\\ & &&\qquad B_4 = \m{ 1 & 2 & 3 & 4 \\ 2 & 2 & 3 & 4 \\ 3 & 3 & 3 & 4 \\ 4 & 4 & 4 & 4 } &&\qquad \det(B_4) = -4\\ &\boxed{n=5} &&\qquad A_5 = \m{ 1 & 1 & 1 & 1 & 1 \\ 1 & 2 & 2 & 2 & 2 \\ 1 & 2 & 3 & 3 & 3 \\ 1 & 2 & 3 & 4 & 4 \\ 1 & 2 & 3 & 4 & 5 } &&\qquad \det(A_5) = 1\\ & &&\qquad B_5 = \m{ 1 & 2 & 3 & 4 & 5 \\ 2 & 2 & 3 & 4 & 5 \\ 3 & 3 & 3 & 4 & 5 \\ 4 & 4 & 4 & 4 & 5 \\ 5 & 5 & 5 & 5 & 5 } &&\qquad \det(B_5) = 5\\ &\boxed{n=6} &&\qquad A_6 = \m{ 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 2 & 2 & 2 & 2 & 2\\ 1 & 2 & 3 & 3 & 3 & 3\\ 1 & 2 & 3 & 4 & 4 & 4\\ 1 & 2 & 3 & 4 & 5 & 5\\ 1 & 2 & 3 & 4 & 5 & 6} &&\qquad \det(A_6) = 1\\ & &&\qquad B_6 = \m{ 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 2 & 3 & 4 & 5 & 6\\ 3 & 3 & 3 & 4 & 5 & 6 \\ 4 & 4 & 4 & 4 & 5 & 6 \\ 5 & 5 & 5 & 5 & 5 & 6 \\ 6 & 6 & 6 & 6 & 6 & 6} &&\qquad \det(B_6) = -6 \end{alignat*}

One reasonably conjectures that $\det(A_n) = 1$ for all $n$ and $\det(B_n) = (-1)^{n-1} n$ for all $n$.

Given $n$, let $L_n=\|l_{ij}\|$, $L’_n=\|l’_{ij}\|$, and $U_n=\|u_{ij}\|$, be $n\times n$ matrices such that $l_{ij}$ equals $1$, if $i\ge j$, and equals $0$, otherwise; $l’_{ij}$ equals $-1$, if $n-1\ge i\ge j$, equals $n$, if $i=n$, and equals $0$, otherwise; $u_{ij}$ equals $1$, if $j\ge i$, and equals $0$, otherwise. It is easy to check that $A_n=L_nU_n$ and $B_n=U_nL’_n$. Since $L_n$, $L’_n$, and $U_n$ are triangular matrices with $1$’s on the main diagonal, $\det L_n=\det U_n=1$ and $\det L’_n=(-1)^{n-1}n$, so $\det A_n=1$ and $\det B_n=(-1)^{n-1}n$. Alternatively, we can observe that $A_n J_n=-L_n$ and $J_nB_n=-L’_n$, where $J_n=-U_n^{-1}$ is an $n\times n$ Jordan cell with the eigenvalue $-1$. Since $\det J_n=(-1)^n$, we obtain the same conclusions.

Let us show the decompositions $A_n=L_nU_n$, $B_n=U_nL_n’$, $A_nJ_n=-L_n$, and $J_nB_n=-L’_n$ for $n=4$: $$ \begin{pmatrix} 1 & 1 & 1 & 1\\ 1 & 2 & 2 & 2\\ 1 & 2 & 3 & 3\\ 1 & 2 & 3 & 4 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 & 0\\ 1 & 1 & 0 & 0\\ 1 & 1 & 1 & 0\\ 1 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 1\\ 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1 \end{pmatrix}, $$

$$ \begin{pmatrix} 1 & 2 & 3 & 4\\ 2 & 2 & 3 & 4\\ 3 & 3 & 3 & 4\\ 4 & 4 & 4 & 4 \end{pmatrix} = \begin{pmatrix} 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 1\\ 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} -1 & 0 & 0 & 0\\ -1 & -1 & 0 & 0\\ -1 & -1 & -1 & 0\\ 4 & 4 & 4 & 4 \end{pmatrix}, $$

$$\begin{pmatrix} 1 & 1 & 1 & 1\\ 1 & 2 & 2 & 2\\ 1 & 2 & 3 & 3\\ 1 & 2 & 3 & 4 \end{pmatrix} \begin{pmatrix} -1 & 1 & 0 & 0\\ 0 & -1 & 1 & 0\\ 0 & 0 & -1 & 1\\ 0 & 0 & 0 & -1 \end{pmatrix} = \begin{pmatrix} -1 & 0 & 0 & 0\\ -1 & -1 & 0 & 0\\ -1 & -1 & -1 & 0\\ -1 & -1 & -1 & -1 \end{pmatrix},$$ $$\begin{pmatrix} -1 & 1 & 0 & 0\\ 0 & -1 & 1 & 0\\ 0 & 0 & -1 & 1\\ 0 & 0 & 0 & -1 \end{pmatrix} \begin{pmatrix} 1 & 2 & 3 & 4\\ 2 & 2 & 3 & 4\\ 3 & 3 & 3 & 4\\ 4 & 4 & 4 & 4 \end{pmatrix} =\begin{pmatrix} 1 & 0 & 0 & 0\\ 1 & 1 & 0 & 0\\ 1 & 1 & 1 & 0\\ -4 & -4 & -4 & -4 \end{pmatrix}.$$

Using the Schur complement,

$$\det \left( {\rm A}_{n+1} \right) = \det \begin{bmatrix} {\rm A}_n & {\rm A}_n \, {\rm e}_n\\ {\rm e}_n^\top {\rm A}_n & n+1 \end{bmatrix} = \underbrace{\left( n + 1 - {\rm e}_n^\top {\rm A}_n {\rm A}_n^{-1} {\rm A}_n \, {\rm e}_n \right)}_{= n + 1 - n} \det \left( {\rm A}_n \right) = \det \left( {\rm A}_n \right)$$

and, since $\det \left( {\rm A}_1 \right) = 1$, we conclude that $\det \left( {\rm A}_n \right) = 1$ for all $n \geq 1$.

$ \newcommand{\m}[1]{\left( \begin{matrix} #1 \end{matrix} \right)} $ An alternate approach for $\det(B_n)$: The Schur Complement:

At the recommendation Rodrigo de Azevedo, I used his approach of the Schur complement -- which they used for $\det(A_n)$ -- in order to determine $\det(B_n)$ and was recommended to post it as a separate answer. We will follow a similar approach here, though it's marginally messier algebraically than in the case of $A_n$.

So, recall: let us write a matrix $M$ as a block matrix by

$$M = \m{A & B \\ C & D }$$

Then provided $A$ is invertible, we have

$$\det(M) = \det(A) \det(D - CA^{-1} B)$$ In the case of $B_n$, we focus on $B_{n+1}$. Recall that, if $e_n$ is the $n$th unit column vector in the usual basis of $\Bbb R^n$, then $Me_n$ gives the $n$th column of $M$ and $e_n^T M$ gives $M$'s $n$th row. With this in mind, we may write

$$B_{n+1} = \left( \begin{matrix} B_{n} & \frac{n+1}{n} B_ne_n\\ \frac{n+1}{n} e_n^T B_n & n+1 \end{matrix} \right)$$

Then the determinant can be found recursively by simplifying the resulting determinant relation. With some minor abuses of notation for simplicity's sake, e.g. treating scalars as analogous to $1 \times 1$ matrices,

\begin{align*} \det(B_{n+1}) &= \det(B_{n}) \det\left( \underbrace{n+1 - \frac{n+1}{n} e_n^T B_n B_{n}^{-1} \frac{n+1}{n} B_n e_n}_{\text{this is a $1\times 1$ matrix, may drop $\det(\cdot)$}} \right)\\ &= \det(B_{n}) \left( n+1 - \left( \frac{n+1}{n} \right)^2 e_n^T \underbrace{B_n B_{n}^{-1} B_n}_{=B_n} e_n \right)\\ &= \det(B_{n}) \left( n+1 - \left( \frac{n+1}{n} \right)^2 e_n^T B_n e_n \right)\\ &= \det(B_{n}) \left( n+1 - \left( \frac{n+1}{n} \right)^2 e_n^T \m{ n \\ \vdots \\ n }\right)\\ &= \det(B_{n}) \left( n+1 - \left( \frac{n+1}{n} \right)^2 n \right)\\ &= \det(B_{n}) \left( - \frac{n+1}{n} \right)\\ \end{align*}

The final equality follows from some basic algebra, but, for completeness:

\begin{align*} n+1 - \left( \frac{n+1}{n} \right)^2 n &= n+1 - \frac{(n+1)^2}{n}\\ &= \frac{n (n+1) - (n+1)^2}{n} \\ &= \frac{n^2 + n -n^2 - 2n - 1}{n^2} \\ &= -\frac{n+1}{n} \end{align*}

A backward-iteration argument in the vein of my original answer's alternate approach, alongside $\det(B_1) = 1$, then allows us to express this by

$$\det(B_n) = \prod_{k=1}^{n-1} \left( - \frac{n+1}{n} \right) = (-1)^{n-1}n$$

as desired.

Another approach that is slightly more involved, but comes at the problem from a different angle and treats both $A_n$ and $B_n$ as special cases of a more general formula. We will actually compute the inverse matrices and relate them to graph laplacians, then use Kirchoff's theorem to eveluate the determinants.

Let $x$ be a variable, and define the $n\times n$ matrix $$L_n(x)=\left(\begin{array}{ccccc} -1 & 1 \\ 1 & -2 & 1\\ \\ &\ddots& \ddots &\ddots\\ && 1 &-2 & 1\\ &&& 1 &-x-1 \end{array}\right)$$

The connection with graph theory is that if we consider the linear graph on $n+1$ nodes, with the edge weight between the last two nodes being equal to x, and the other edge weights equal to 1, then $L_n$ is equal to the corresponding graph Laplacian with the last row and column removed (and opposite the usual sign convention). As a consequence, we get the following:

Lemma $det(L_n(x))=(-1)^nx$

Proof Follows from Kirchoff's theorem about spanning trees. Since the graph is linear, it has only a single spanning tree, and the weighting is $(1)^nx$. The factor of $(-1)^n$ arises because we are using the opposite of the usual sign convention.

Now let us compute $L_n^{-1}$. We use the block decomposition $$L_n=\left(\begin{array}{cc} L_{n-1}(1) & e_{n-1} \\ e_{n-1}^t & -x-1\end{array}\right):=\left(\begin{array}{cc} A & B \\ C & D\end{array}\right)$$ where $e_{n-1}$ denotes the vector of length $n-1$ with a 1 in the last entry and 0 elsewhere.

Now apply the formula for the inverse of a block matrix. The main observation is that $A\textbf{1}=-e_{n-1}$, so that $A^{-1}e_{n-1}=-\textbf{1}$. The remaining calculations are routine, with the final result being

$$L_n^{-1}(x)=\left(\begin{array}{cc} L_{n-1}^{-1}(1) -\textbf{1}\textbf{1}^t/x& -\textbf{1}/x \\ -\textbf{1}/x & -1/x\end{array}\right)=\left(\begin{array}{cc} L_{n-1}(1)^{-1} & 0 \\ 0 & 0\end{array}\right)-\textbf{1}\textbf{1}^t/x$$

If we set $x=1$ then we get a recurrence for $L_{n}^{-1}(1)$, and it easily follows by induction that the solution is $(L_{n}^{-1}(1))_{ij}=-\min(n-i+1,n-j+1)$.

Computing $\det(A_n):$

By the previous discussion, we can write $A_n=-P^t(L_n^{-1}(1))P$ where $P$ is the permutation matrix the reverses the order of the rows. Conjugating does not change the determinant, so applying the Lemma, $det(A_n)=(-1)^n det(L_n(1))^{-1}=(-1)^n(-1)^n=1$.

Computing $\det(B_n):$

For $1\leq i,j\leq n$, observe that $max(i,j)=-min(n-i,n-j)+n=((L_{n-1}(1))^{-1})_{ij}+n$. Thus $$B_n=\left(\begin{array}{cc} L_{n-1}(1)^{-1} & 0 \\ 0 & 0\end{array}\right)+n\textbf{1}\textbf{1}^t$$

and therefore $B_n=L_n(-1/n)^{-1}$. By the lemma, $det(B_n)=1/det(L_n(-1/n))=n(-1)^{n+1}$.

$ \newcommand{\RR}{\mathcal{R}} \newcommand{\m}[1]{\left( \begin{matrix} #1 \end{matrix} \right)} \newcommand{\mdet}[1]{\left| \begin{matrix} #1 \end{matrix} \right|} $ Finding $\det(A_n)$:

I will pursue this one in part by simple row reduction: adding multiples of one row to another will preserve the determinant. So, for now, note the form of $A_n$:

$$A_n = \m{ 1 & 1 & 1 & \cdots & 1 \\ 1 & 2 & 2 & \cdots & 2 \\ 1 & 2 & 3 & \cdots & 3 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & 2 & 3 & \cdots & n}$$

Throughout the entirety of this answer, let $\RR_i$ denote the $i$th row of the matrix, at whatever stage in the row reduction process we're at. We'll let $\sim$ denote equivalence by row reduction. At this point, subtract $\RR_1$ from each of $\RR_k$ for $k \ge 2$. We see that

$$A_n \sim \m{ 1 & 1 & 1 & \cdots & 1 \\ 0 & 1 & 1 & \cdots & 1 \\ 0 & 1 & 2 & \cdots & 2 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 1 & 2 & \cdots & n-1}$$

Next, subtract $\RR_2$ from $\RR_1$. Then

$$A_n \sim \m{ 1 & 0 & 0 & \cdots & 0 \\ 0 & 1 & 1 & \cdots & 1 \\ 0 & 1 & 2 & \cdots & 2 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 1 & 2 & \cdots & n-1}$$

Expanding the determinant along the first row (or column) trivially yields that

$$\det(A_n) = 1 \cdot \mdet{ 1 & 1 & 1 & \cdots & 1 \\ 1 & 2 & 2 & \cdots & 2 \\ 1 & 2 & 3 & \cdots & 3 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & 2 & 3 & \cdots & n-1} = \det(A_{n-1})$$

This readily defines a linear homogenous recurrence relation, with initial condition $\det(A_1) = 1$, which sufficiently verifies that $\det(A_n) = 1$ for all $n \in \Bbb Z^+$. (This is particularly clear on back-iteration, which shows $\det(A_n) = \det(A_k)$ for $k \in \{1,2,\cdots,n-1\}$.)

Finding $\det(B_n)$:

I will similarly utilize row reduction for this, as I did for $A_n$. In general, $B_n$ looks like this:

$$B_n = \m{ 1 & 2 & 3 & \cdots & n \\ 2 & 2 & 3 & \cdots & n \\ 3 & 3 & 3 & \cdots & n \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ n & n & n & \cdots & n}$$

Subtract $\RR_2$ from $\RR_1$ and we obtain

$$B_n \sim \m{ -1 & 0 & 0 & \cdots & 0 \\ 2 & 2 & 3 & \cdots & n \\ 3 & 3 & 3 & \cdots & n \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ n & n & n & \cdots & n}$$

Next, add $k \RR_1$ to each $\RR_k$ for $k \ge 2$:

$$B_n \sim \m{ -1 & 0 & 0 & \cdots & 0 \\ 0 & 2 & 3 & \cdots & n \\ 0 & 3 & 3 & \cdots & n \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & n & n & \cdots & n}$$

Similarly, subtract $\RR_3$ from $\RR_2$, and then add $k \RR_2$ to each $\RR_k$ for $k \ge 3$.

$$B_n \sim \m{ -1 & 0 & 0 & \cdots & 0 \\ 0 & -1 & 0 & \cdots &0 \\ 0 & 0 & 3 & \cdots & n \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & n & \cdots & n}$$

We proceed inductively. At the $r$th step, we subtract $\RR_{r+1}$ from $\RR_r$, turning $\RR_r$ into a row vector with all zeroes except $-1$ in its $r$th position. Then we add $k$ times this new $\RR_r$ to each $\RR_i$ with $i > k$, to negate their $r$th column and turn it into a similar row vector.

At the end of this process, after the $(n-1)$th step, we have that

$$B_n \sim \m{ -1 & 0 & 0 & \cdots & 0 \\ 0 & -1 & 0 & \cdots & 0 \\ 0 & 0 & -1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & n} = \mathrm{diag}(\underbrace{-1,-1,-1,\cdots,-1,-1}_{n-1 \; (-1)'s},n)$$

The determinant of $B_n$ is that of this diagonal matrix, and the determinant of a diagonal matrix is the product of the entries on the diagonal. Thus,

$$\det(B_n) = (-1)^{n-1} n$$

Alternate Method for $\det(B_n)$:

This still utilizes row reduction, but more in line with how Dr. Peyam did it for $B_5$ in his video. So we instead subtract $\frac{n}{n-1} \RR_{n-1}$ from $\RR_n$. Then

\begin{align*} B_n &= \m{ 1 & 2 & 3 & \cdots & n-1 & n \\ 2 & 2 & 3 & \cdots & n-1 & n \\ 3 & 3 & 3 & \cdots & n-1 & n \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ n-1 & n-1 & n-1 & \cdots & n-1 & n \\ n & n & n & \cdots & n & n} \\ &\sim \m{ 1 & 2 & 3 & \cdots & n-1 & n \\ 2 & 2 & 3 & \cdots & n-1 & n \\ 3 & 3 & 3 & \cdots & n-1 & n \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ n-1 & n-1 & n-1 & \cdots & n-1 & n \\ 0 & 0 & 0 & \cdots & 0 & n - \frac{n^2}{n-1} } \end{align*}

We expand the determinant along the bottom row. Since the only nonzero entry is the bottom-right entry (i.e. $b_{n,n}^{(n)})$), the sign associated with this expansion is simply $+1$. (The sign of this in the cofactor expansion is more formally $(-1)^{n+n}=(-1)^{2n} = 1$, since the exponent is even.)

Thus,

\begin{align*} \det{B_n} &= \left( n - \frac{n^2}{n-1} \right) \mdet{ 1 & 2 & 3 & \cdots & n-1 \\ 2 & 2 & 3 & \cdots & n-1 \\ 3 & 3 & 3 & \cdots & n-1 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ n-1 & n-1 & n-1 & \cdots & n-1 } \\ &= \left( n - \frac{n^2}{n-1} \right) \det(B_{n-1}) \end{align*}

Visibly, one may proceed inductively, iterating backwards to the initial condition of $\det(B_1) = 1$, and observe

$$\det(B_n) = \prod_{k=2}^{n} \left( k - \frac{k^2}{k-1} \right)$$

One now notes that

$$ k - \frac{k^2}{k-1} = \frac{k(k-1) - k^2}{k-1} = \frac{k^2 - k - k^2}{k-1} = -\frac{k}{k-1}$$

and thus

$$\det(B_n) = \prod_{k=2}^{n} \left( -\frac{k}{k-1} \right)$$

This is a telescoping product, insofar as consecutive terms cancel nicely. Writing out the product, we have

\begin{align*} \require{cancel} \prod_{k=2}^{n} \frac{k}{k-1} &= \frac 2 1 \cdot \frac 3 2 \cdot \frac 4 3 \cdot \frac 5 4 \cdot \cdots \cdot \frac{n-2}{n-3} \cdot \frac{n-1}{n-2} \cdot \frac{n}{n-1}\\ &= \frac{\cancel{2}} 1 \cdot \frac {\cancel{3}} {\cancel{2}} \cdot \frac {\cancel{4}} {\cancel{3}} \cdot \frac {\cancel{5}} {\cancel{4}} \cdot \cdots \cdot \frac{\cancel {n-2}}{\cancel {n-3}} \cdot \frac{\cancel{n-1}}{\cancel {n-2}} \cdot \frac{n}{\cancel{n-1}}\\ &= n \end{align*}

Meanwhile, what remains now is the sign. Since it is constant with respect to $k$, we can pull it out of the product altogether. Note that the product has $n-1$ members. Thus,

$$\det(B_n) = (-1)^{n-1} \prod_{k=2}^{n} \frac{k}{k-1} = (-1)^{n-1} n$$

as desired.