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

Question

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

Answer 1

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}$.

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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}.$$

Answer 6

The inductive approach (IE How I first dealt with them when I saw them)
Using notation from Eevee Trainer.

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

Now, expanding along the first column, we see that $\det(A_n) = 1 \times \det(A_{n-1})$.
Since $ \det (A_1) = 1$, hence $\det (A_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}$$

At this point, subtract $\RR_n$ from each of $\RR_k$ for $k \leq n-1$. We see that

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

Expanding along the last column, $ \det B_n = n \times \det C_{n-1}$, where $C_n$ is the $(n-1) \times (n-1)$ minor.
Multiplying each of the columns by $ (-1)$, we get that

$$\det(C_n) = ( -1)^{n-1} \det \m{ n-1 & n-2 & n-3 & \cdots & 1 \\ n-2 & n-2 & n-3 & \cdots & 1 \\ n-3 & n-3 & n-3 & \cdots &1 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & 1 & \cdots & 1}$$

Note that the matrix on the RHS is just $A_{n-1}$, though with the rows and columns completely flipped. Hence, by accounting for the flip, the determinant is $ (-1)^{2(n-2) } \det(A_n) = 1 $.

Hence, $ \det (B_n) = n \times \det (C_{n-1}) = n \times (-1)^{n-1} \times 1 $.

Answer 7

Here's an alternative way to think about $A_n$ using probability.

Let $X_i$ be a collection of independent unit gaussians, and let $S_i:=\sum_{k\leq i} X_k$ be the running sum. Define $Y_n=(S_1, \dots, S_n)$. Then $Y_n$ is multivariate gaussian, and it is easy to check that the covariance matrix is $A_n$.

The key observation is that $S_n-S_{n-1}$ is independent of $Y_{n-1}$. This is because $S_n-S_{n-1}=X_n$, while $Y_n$ depends only on $\{X_i\}_{i<n}$. Therefore, we can expand the probability density as follows:

\begin{align*} P(Y_n) &=P(Y_n \mid Y_{n-1})P(Y_{n-1})\\ &=P(S_n-S_{n-1} \mid Y_{n-1})P(Y_{n-1})\\ &=(2\pi)^{-1/2}e^{-(S_n-S_{n-1})^2/2}P(Y_{n-1}) \end{align*}

On the other hand, $P(Y_n)=(2\pi)^{-n/2}\det(A_n)^{-1/2}e^{-Y_n^tA_n^{-1}Y_n/2}$ so

$$e^{-Y_n^tA_n^{-1}Y_n/2}\det(A_n)^{-1/2}=e^{-(S_n-S_{n-1})^2/2}e^{-Y_{n-1}^tA_{n-1}^{-1}Y_{n-1}/2}\det(A_{n-1})^{-1/2}$$

where we have cancelled the common factor of $(2\pi)^{-n/2}$.

Thus formula holds for any value of $Y_n$, so set $Y_n=(0,\dots,0)$. Plugging into the above formula we conclude that $\det(A_n)=\det(A_{n-1})$. Obviously $\det(A_1)=1$ so we are done.

Answer 8

These conjectures are correct and can be proved by reducing the determinants to suitable triangular forms to determine the exact values.

Setup of the problem

Consider two $n \times n$ matrices $A_n$ and $B_n$ defined by the 2 dimensional sequences defined on positive integers $\mathbb{Z}^+$, or natural numbers where $\mathbb{Z}^+ = \mathbb{N} = \{1,2,3,\cdots\}$. The sequences are $a_{i,j}^{(n)}$ and $b_{i,j}^{(n)}$ defined by the following relations;

$$ a_{i,j}^{(n)} := \min\{i,j\} \quad \quad b_{i,j}^{(n)} := \max\{i,j\} \quad \quad \forall i,j \leq n \in \mathbb{Z}^+ $$

The generalized matrices are thus defined by the following templates;

$$ A_n:= \begin{pmatrix} a_{i,j}^{(n)} \end{pmatrix}_ {i,j = 1, 2, ..., n} = \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 & 1\\ 1 & 2 & 2 & \cdots & 2 & 2\\ 1 & 2 & 3 & \cdots & 3 & 3\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 1 & 2 & 3 & \cdots & n-1 & n-1\\ 1 & 2 & 3 & \cdots & n-1 & n\\ \end{bmatrix} $$

$$ B_n:= \begin{pmatrix} b_{i,j}^{(n)} \end{pmatrix}_ {i,j = 1, 2, ..., n} = \begin{bmatrix} 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\\ \end{bmatrix} $$

Proof for $\det{A_n}$

Consider the determinant of the matrix $A_n$;

$$ \det{A_n} = \begin{vmatrix} 1 & 1 & 1 & \cdots & 1 & 1\\ 1 & 2 & 2 & \cdots & 2 & 2\\ 1 & 2 & 3 & \cdots & 3 & 3\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 1 & 2 & 3 & \cdots & n-1 & n-1\\ 1 & 2 & 3 & \cdots & n-1 & n\\ \end{vmatrix} $$

Subtracting the $(n-1)^{th}$ row from the $n^{th}$ row. $\mathcal{R}_n := \mathcal{R}_n - \mathcal{R}_{n-1}$

$$ \det{A_n} = \begin{vmatrix} 1 & 1 & 1 & \cdots & 1 & 1\\ 1 & 2 & 2 & \cdots & 2 & 2\\ 1 & 2 & 3 & \cdots & 3 & 3\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 1 & 2 & 3 & \cdots & n-1 & n-1\\ 0 & 0 & 0 & \cdots & 0 & 1\\ \end{vmatrix} $$

Next subtract the $(n-2)^{th}$ row from the $(n-1)^{th}$ row. $\mathcal{R}_{n-1} := \mathcal{R}_{n-1} - \mathcal{R}_{n-2}$

$$ \det{A_n} = \begin{vmatrix} 1 & 1 & 1 & \cdots & 1 & 1\\ 1 & 2 & 2 & \cdots & 2 & 2\\ 1 & 2 & 3 & \cdots & 3 & 3\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & 0 & \cdots & 1 & 1\\ 0 & 0 & 0 & \cdots & 0 & 1\\ \end{vmatrix} $$

Similarly, following this pattern upward of removing the previous row from the current row, upto the second row. $\mathcal{R}_{i} := \mathcal{R}_{i} - \mathcal{R}_{i-1} \quad \forall i=2,3,\cdots,n$

$$ \det{A_n} = \begin{vmatrix} 1 & 1 & 1 & \cdots & 1 & 1\\ 1 & 2 & 2 & \cdots & 2 & 2\\ 1 & 2 & 3 & \cdots & 3 & 3\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & 0 & \cdots & 1 & 1\\ 0 & 0 & 0 & \cdots & 0 & 1\\ \end{vmatrix} = \cdots = \begin{vmatrix} 1 & 1 & 1 & \cdots & 1 & 1\\ 1 & 2 & 2 & \cdots & 2 & 2\\ 0 & 0 & 1 & \cdots & 1 & 1\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & 0 & \cdots & 1 & 1\\ 0 & 0 & 0 & \cdots & 0 & 1\\ \end{vmatrix} = \begin{vmatrix} 1 & 1 & 1 & \cdots & 1 & 1\\ 0 & 1 & 1 & \cdots & 1 & 1\\ 0 & 0 & 1 & \cdots & 1 & 1\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & 0 & \cdots & 1 & 1\\ 0 & 0 & 0 & \cdots & 0 & 1\\ \end{vmatrix} $$

Finally an upper triangular matrix is left after performing these $(n-1)$ row operations of subtracting the previous from each row. The sequence in which these operations are performed is important starting from the last row upwards to the second row. The upper triangular matrix has all $1's$ in the upper triangle and all $0's$ below the diagonal. The determinant of a triangular matrix is the product of the entries of the diagonal. Thus;

$$ \det{A_n}=\begin{vmatrix} 1 & 1 & 1 & \cdots & 1 & 1\\ 0 & 1 & 1 & \cdots & 1 & 1\\ 0 & 0 & 1 & \cdots & 1 & 1\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & 0 & \cdots & 1 & 1\\ 0 & 0 & 0 & \cdots & 0 & 1\\ \end{vmatrix} = (1)^n=1 \quad \blacksquare $$

Proof for $\det{B_n}$

For the proof of the determinant of $B_n$ we will follow a similar approach as for the previous case. We will try to convert the determinant into a triangular form through elementary row operations.

$$ \det{B_n}= \begin{vmatrix} 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\\ \end{vmatrix} $$

Subtracting the $(n-1)^{th}$ row from the $n^{th}$ row. $\mathcal{R}_n := \mathcal{R}_n - \mathcal{R}_{n-1}$

$$ \det{B_n}= \begin{vmatrix} 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\\ 1 & 1 & 1 & \cdots & 1 & 0\\ \end{vmatrix} $$

Next subtract the $(n-2)^{th}$ row from the $(n-1)^{th}$ row. $\mathcal{R}_{n-1} := \mathcal{R}_{n-1} - \mathcal{R}_{n-2}$

$$ \det{B_n}= \begin{vmatrix} 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\\ 1 & 1 & 1 & \cdots & 0 & 0\\ 1 & 1 & 1 & \cdots & 1 & 0\\ \end{vmatrix} $$

Similarly, following this pattern upward of removing the previous row from the current row, upto the second row. $\mathcal{R}_{i} := \mathcal{R}_{i} - \mathcal{R}_{i-1} \quad \forall i=2,3,\cdots,n$

$$ \det{B_n} = \begin{vmatrix} 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\\ 1 & 1 & 1 & \cdots & 0 & 0\\ 1 & 1 & 1 & \cdots & 1 & 0\\ \end{vmatrix} = \cdots = \begin{vmatrix} 1 & 2 & 3 & \cdots & n-1 & n\\ 2 & 2 & 3 & \cdots & n-1 & n\\ 1 & 1 & 0 & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 1 & 1 & 1 & \cdots & 0 & 0\\ 1 & 1 & 1 & \cdots & 1 & 0\\ \end{vmatrix} = \begin{vmatrix} 1 & 2 & 3 & \cdots & n-1 & n\\ 1 & 0 & 0 & \cdots & 0 & 0\\ 1 & 1 & 0 & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 1 & 1 & 1 & \cdots & 0 & 0\\ 1 & 1 & 1 & \cdots & 1 & 0\\ \end{vmatrix} $$

In order to convert this into a triangular form, the first row must be bought all the way to the bottom, while shifting every other row up by $1$. This is performed by consecutive swapping of 2 rows. Recall that every row swap flips the sign of the determinant of the matrix, thus;

$$ \det{B_n} = \begin{vmatrix} 1 & 2 & 3 & \cdots & n-1 & n\\ 1 & 0 & 0 & \cdots & 0 & 0\\ 1 & 1 & 0 & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 1 & 1 & 1 & \cdots & 0 & 0\\ 1 & 1 & 1 & \cdots & 1 & 0\\ \end{vmatrix} $$

Swapping $1^{st}$ and $2^{nd}$ rows gives the following. $\mathcal{R}_{1} <=> \mathcal{R}_{2}$

$$ \det{B_n} = (-1) \begin{vmatrix} 1 & 0 & 0 & \cdots & 0 & 0\\ 1 & 2 & 3 & \cdots & n-1 & n\\ 1 & 1 & 0 & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 1 & 1 & 1 & \cdots & 0 & 0\\ 1 & 1 & 1 & \cdots & 1 & 0\\ \end{vmatrix} $$

Next swap the $2^{nd}$ and $3^{rd}$ rows. $\mathcal{R}_{2} <=> \mathcal{R}_{3}$

$$ \det{B_n} = (-1)^{2} \begin{vmatrix} 1 & 0 & 0 & \cdots & 0 & 0\\ 1 & 1 & 0 & \cdots & 0 & 0\\ 1 & 2 & 3 & \cdots & n-1 & n\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 1 & 1 & 1 & \cdots & 0 & 0\\ 1 & 1 & 1 & \cdots & 1 & 0\\ \end{vmatrix} $$

Similarly continue this pattern of swapping the rows $(n-1)$ times in total till the last two rows. $\mathcal{R}_{i} <=> \mathcal{R}_{i+1} \quad \forall i=1,2,\cdots,n-1$

$$ \det{B_n} = (-1)^{2} \begin{vmatrix} 1 & 0 & 0 & \cdots & 0 & 0\\ 1 & 1 & 0 & \cdots & 0 & 0\\ 1 & 2 & 3 & \cdots & n-1 & n\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 1 & 1 & 1 & \cdots & 0 & 0\\ 1 & 1 & 1 & \cdots & 1 & 0\\ \end{vmatrix} = (-1)^{3} \begin{vmatrix} 1 & 0 & 0 & \cdots & 0 & 0\\ 1 & 1 & 0 & \cdots & 0 & 0\\ 1 & 1 & 1 & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 1 & 1 & 1 & \cdots & 0 & 0\\ 1 & 1 & 1 & \cdots & 1 & 0\\ \end{vmatrix} = \cdots = (-1)^{n-2} \begin{vmatrix} 1 & 0 & 0 & \cdots & 0 & 0\\ 1 & 1 & 0 & \cdots & 0 & 0\\ 1 & 1 & 1 & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 1 & 2 & 3 & \cdots & n-1 & n\\ 1 & 1 & 1 & \cdots & 1 & 0\\ \end{vmatrix} = (-1)^{n-1} \begin{vmatrix} 1 & 0 & 0 & \cdots & 0 & 0\\ 1 & 1 & 0 & \cdots & 0 & 0\\ 1 & 1 & 1 & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 1 & 1 & 1 & \cdots & 1 & 0\\ 1 & 2 & 3 & \cdots & n-1 & n\\ \end{vmatrix} $$

This determinant is finally in a lower triangular form. The sequence of swaps between two consecutive rows starting from the first two rows down to the last two rows is important to bring this matrix into the triangular form as shown above. The lower triangular matrix contains all $0’s$ above the diagonal. It contains all $1’s$ in the lower triangle except for the last row. The last row contains entries from $1$ to $n$ in column numbers $1$ to $n$ respectively. Since the determinant of a triangular matrix is the product of the diagonal entries, thus;

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

But these hold true for any positive integer value of $n$ and thus the conjectures hold true for any $n\in \mathbb{Z}^+$.

Answer 9

Using the Schur complement,

$$\det \left( {\rm B}_{n+1} \right) = \det \begin{bmatrix} {\rm B}_n & (n+1) {\Bbb 1}_n\\ (n+1) {\Bbb 1}_n^\top & n+1 \end{bmatrix} = \underbrace{\left( n + 1 - (n + 1)^2 {\Bbb 1}_n^\top {\rm B}_n^{-1} {\Bbb 1}_n \right)}_{= -\left(\frac{n+1}{n}\right)} \det \left( {\rm B}_n \right)$$

or, alternatively,

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

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