Skip to main content
MathOverflow

Return to Answer

Formula now valid for all $m$ and $n$, also cleaned up proof and addressed the general case explicitly
Source Link
or43
or43
  • 161
  • 2

A partial answer: for fixed $m$, I provide a formulaEdited to computegive a polynomial expression formore complete $D_m(n)$(and cleaner) answer valid for all $n \geq m+1$. I'm not immediately sure if the expression will still be valid for $n < m+1$$m, n$. This approach also worksMy original answer only applied for a general polynomial in $j, k$$n \geq m+1$, not just one ofand only went through the formproof for the case of $(j-k)^m$$(x-y)^m$.

Let $v$ be the all-ones vector, $J = vv^T$ the all-ones matrix, $D$ the diagonal matrix with diagonal entriesSay we have a polynomial $1, 2, \dots, n$$P(x, y) = \sum_{0 \leq a, b \leq m} c_{ab} x^a y^b$, and $A = ((j-k)^m)_{1 \leq j, k \leq n}$, so we want to compute $\det(A + I)$. Note that for as a given matrixfunction of $M = (m_{jk})_{1 \leq j, k \leq n}$$n$, we havefor $DM = (jm_{jk})_{1 \leq j, k \leq n}$ and$A = A(n) = (P(j, k))_{1 \leq j, k \leq n}$. Let $MD = (km_{jk})_{1 \leq j, k \leq n}$$C = (c_{ab})_{0 \leq a, b \leq m}$, so it follows that $$A = \sum_{r=0}^m (-1)^{m-r} \binom{m}{r} D^r J D^{m-r}.$$

The matrixand let $T$ with columns$V$ be the $v, Dv, \dots, D^{n-1}v$ is a Vandermonde$n \times (m+1)$ matrix with nonzero determinantcolumns $v_0, v_1, \dots, v_m$, so these vectors form a basis. Considerwhere $v_d$ is the action ofvector with $A$ on this basis: we have $$AD^kv = \sum_{r=0}^m (-1)^{m-r} \binom{m}{r} D^r v v^T D^{m-r+k} v = \sum_{r=0}^m (-1)^{m-r} \binom{m}{r} s_{m-r+k}(n) D^r v$$ where$j$-th entry $s_p(n) := \sum_{k=1}^n k^p = v^TD^p v$$j^d$ for $1 \leq j \leq n$. Then if $B = (b_{jk})_{0 \leq j, k \leq n-1} = T^{-1}AT$$v_a v_b^T$ is the matrix of $A$$n \times n$ matrix with respect to this basis (note the indices start at$(j, k)$-entry $0$)$j^a k^b$, so it follows that $$b_{jk} = \begin{cases} (-1)^{m-j} \binom{m}{j} s_{m-j+k}(n) & j \leq m \\ 0 & j > m \end{cases}$$$$A = \sum_{0 \leq a, b \leq m} c_{ab} v_a v_b^T = VCV^T$$ Nowand thus by the $\det(A+I) = \det(B+I)$Weinstein-Aronszajn identity $$\det(A + I) = \det(VCV^T + I) = \det(CV^TV + I) = \det(CS + I),$$ where $S = V^T V$. Note that $C$, but since all entries of $B+I$ below the first$S$, and hence also $m+1$ rows$CS+I$ are $0$ except the$(m+1) \times (m+1)$.

Now, for $1$'s on the diagonal$0 \leq a, b \leq m$, the determinant$(a, b)$-entry of $B+I$$S$ is the same as the determinant of its upper-left $(m+1) \times (m+1)$ submatrix$v_a^T v_b = s_{a+b}(n)$, so $$D_m(n) = \det\left((-1)^{m-j} \tbinom{m}{j} s_{m-j+k}(n) + \delta_{jk}\right)_{0 \leq j, k \leq m}.$$

where $s_d(n) := \sum_{j=1}^n j^d$. Since each $s_p(n)$ is$s_d(n)$ can be expressed as a polynomial in $n$ of degree $p+1$, and$d+1$ $m$ is constant(with rational coefficients), this gives an expressionall entries of $D_m(n)$$CS+I$ are fixed polynomials in $n$, and thus the equation above expresses $\det(A+I)$ as a polynomial in $n$ (with rational coefficients), valid at least for when all $n \geq m+1$$c_{ab}$ are rational). The

In the case of $P(x, y) = (x-y)^m$, the resulting formula is $$D_m(n) = \det\left((-1)^{m-a} \tbinom{m}{a} s_{m-a+b}(n) + \delta_{ab}\right)_{0 \leq a, b \leq m}.$$ In this case, the degree of each term in the expansion of the determinant is $(m+1)^2$, so $D_m(n)$ has degree at most $(m+1)^2$. The calculated polynomial agrees with yours for $m=1$ and $m=2$, I haven't checked $m=3$ yet.

A partial answer: for fixed $m$, I provide a formula to compute a polynomial expression for $D_m(n)$ valid for all $n \geq m+1$. I'm not immediately sure if the expression will still be valid for $n < m+1$. This approach also works for a general polynomial in $j, k$, not just one of the form $(j-k)^m$.

Let $v$ be the all-ones vector, $J = vv^T$ the all-ones matrix, $D$ the diagonal matrix with diagonal entries $1, 2, \dots, n$, and $A = ((j-k)^m)_{1 \leq j, k \leq n}$, so we want to compute $\det(A + I)$. Note that for a given matrix $M = (m_{jk})_{1 \leq j, k \leq n}$, we have $DM = (jm_{jk})_{1 \leq j, k \leq n}$ and $MD = (km_{jk})_{1 \leq j, k \leq n}$, so it follows that $$A = \sum_{r=0}^m (-1)^{m-r} \binom{m}{r} D^r J D^{m-r}.$$

The matrix $T$ with columns $v, Dv, \dots, D^{n-1}v$ is a Vandermonde matrix with nonzero determinant, so these vectors form a basis. Consider the action of $A$ on this basis: we have $$AD^kv = \sum_{r=0}^m (-1)^{m-r} \binom{m}{r} D^r v v^T D^{m-r+k} v = \sum_{r=0}^m (-1)^{m-r} \binom{m}{r} s_{m-r+k}(n) D^r v$$ where $s_p(n) := \sum_{k=1}^n k^p = v^TD^p v$. Then if $B = (b_{jk})_{0 \leq j, k \leq n-1} = T^{-1}AT$ is the matrix of $A$ with respect to this basis (note the indices start at $0$), $$b_{jk} = \begin{cases} (-1)^{m-j} \binom{m}{j} s_{m-j+k}(n) & j \leq m \\ 0 & j > m \end{cases}$$ Now $\det(A+I) = \det(B+I)$, but since all entries of $B+I$ below the first $m+1$ rows are $0$ except the $1$'s on the diagonal, the determinant of $B+I$ is the same as the determinant of its upper-left $(m+1) \times (m+1)$ submatrix, so $$D_m(n) = \det\left((-1)^{m-j} \tbinom{m}{j} s_{m-j+k}(n) + \delta_{jk}\right)_{0 \leq j, k \leq m}.$$

Since each $s_p(n)$ is a polynomial in $n$ of degree $p+1$, and $m$ is constant, this gives an expression of $D_m(n)$ as a polynomial in $n$ (with rational coefficients), valid at least for all $n \geq m+1$. The degree of each term in the expansion of the determinant is $(m+1)^2$, so $D_m(n)$ has degree at most $(m+1)^2$. The calculated polynomial agrees with yours for $m=1$ and $m=2$, I haven't checked $m=3$ yet.

Edited to give a more complete (and cleaner) answer valid for all $m, n$. My original answer only applied for $n \geq m+1$, and only went through the proof for the case of $(x-y)^m$.

Say we have a polynomial $P(x, y) = \sum_{0 \leq a, b \leq m} c_{ab} x^a y^b$, and want to compute $\det(A + I)$ as a function of $n$, for $A = A(n) = (P(j, k))_{1 \leq j, k \leq n}$. Let $C = (c_{ab})_{0 \leq a, b \leq m}$, and let $V$ be the $n \times (m+1)$ matrix with columns $v_0, v_1, \dots, v_m$, where $v_d$ is the vector with $j$-th entry $j^d$ for $1 \leq j \leq n$. Then $v_a v_b^T$ is the $n \times n$ matrix with $(j, k)$-entry $j^a k^b$, so it follows that $$A = \sum_{0 \leq a, b \leq m} c_{ab} v_a v_b^T = VCV^T$$ and thus by the Weinstein-Aronszajn identity $$\det(A + I) = \det(VCV^T + I) = \det(CV^TV + I) = \det(CS + I),$$ where $S = V^T V$. Note that $C$, $S$, and hence also $CS+I$ are $(m+1) \times (m+1)$.

Now, for $0 \leq a, b \leq m$, the $(a, b)$-entry of $S$ is $v_a^T v_b = s_{a+b}(n)$, where $s_d(n) := \sum_{j=1}^n j^d$. Since each $s_d(n)$ can be expressed as a polynomial in $n$ of degree $d+1$ (with rational coefficients), all entries of $CS+I$ are fixed polynomials in $n$, and thus the equation above expresses $\det(A+I)$ as a polynomial in $n$ (with rational coefficients when all $c_{ab}$ are rational).

In the case of $P(x, y) = (x-y)^m$, the resulting formula is $$D_m(n) = \det\left((-1)^{m-a} \tbinom{m}{a} s_{m-a+b}(n) + \delta_{ab}\right)_{0 \leq a, b \leq m}.$$ In this case, the degree of each term in the expansion of the determinant is $(m+1)^2$, so $D_m(n)$ has degree at most $(m+1)^2$. The calculated polynomial agrees with yours for $m=1$ and $m=2$, I haven't checked $m=3$ yet.

Source Link
or43
or43
  • 161
  • 2

A partial answer: for fixed $m$, I provide a formula to compute a polynomial expression for $D_m(n)$ valid for all $n \geq m+1$. I'm not immediately sure if the expression will still be valid for $n < m+1$. This approach also works for a general polynomial in $j, k$, not just one of the form $(j-k)^m$.

Let $v$ be the all-ones vector, $J = vv^T$ the all-ones matrix, $D$ the diagonal matrix with diagonal entries $1, 2, \dots, n$, and $A = ((j-k)^m)_{1 \leq j, k \leq n}$, so we want to compute $\det(A + I)$. Note that for a given matrix $M = (m_{jk})_{1 \leq j, k \leq n}$, we have $DM = (jm_{jk})_{1 \leq j, k \leq n}$ and $MD = (km_{jk})_{1 \leq j, k \leq n}$, so it follows that $$A = \sum_{r=0}^m (-1)^{m-r} \binom{m}{r} D^r J D^{m-r}.$$

The matrix $T$ with columns $v, Dv, \dots, D^{n-1}v$ is a Vandermonde matrix with nonzero determinant, so these vectors form a basis. Consider the action of $A$ on this basis: we have $$AD^kv = \sum_{r=0}^m (-1)^{m-r} \binom{m}{r} D^r v v^T D^{m-r+k} v = \sum_{r=0}^m (-1)^{m-r} \binom{m}{r} s_{m-r+k}(n) D^r v$$ where $s_p(n) := \sum_{k=1}^n k^p = v^TD^p v$. Then if $B = (b_{jk})_{0 \leq j, k \leq n-1} = T^{-1}AT$ is the matrix of $A$ with respect to this basis (note the indices start at $0$), $$b_{jk} = \begin{cases} (-1)^{m-j} \binom{m}{j} s_{m-j+k}(n) & j \leq m \\ 0 & j > m \end{cases}$$ Now $\det(A+I) = \det(B+I)$, but since all entries of $B+I$ below the first $m+1$ rows are $0$ except the $1$'s on the diagonal, the determinant of $B+I$ is the same as the determinant of its upper-left $(m+1) \times (m+1)$ submatrix, so $$D_m(n) = \det\left((-1)^{m-j} \tbinom{m}{j} s_{m-j+k}(n) + \delta_{jk}\right)_{0 \leq j, k \leq m}.$$

Since each $s_p(n)$ is a polynomial in $n$ of degree $p+1$, and $m$ is constant, this gives an expression of $D_m(n)$ as a polynomial in $n$ (with rational coefficients), valid at least for all $n \geq m+1$. The degree of each term in the expansion of the determinant is $(m+1)^2$, so $D_m(n)$ has degree at most $(m+1)^2$. The calculated polynomial agrees with yours for $m=1$ and $m=2$, I haven't checked $m=3$ yet.