24
$\begingroup$

Let $d \geq 2$ be an integer and $\xi=\exp(\frac{2\pi i}{d})$. I am trying to compute the determinant of the matrix $$ (\xi^{ij}-1)_{1 \leq i, j \leq d-1}. $$ Let me call it $\Delta(d)$. For small values of $d$ I get:

    $\Delta(2)=-2$
    $\Delta(3)=-3\sqrt{3}i$
    $\Delta(4)=-16i$

But I can't seem to find a general formula. How can I do this?

$\endgroup$
6
  • 2
    $\begingroup$ Looks like you can obtain this matrix starting from the Fourier matrix (Vandermonde on roots of unity) and doing a few elementary row operations to subtract the all-ones first row from every other row. This should give you a method to reduce this determinant to the Vandermonde one. $\endgroup$ Jun 23, 2017 at 15:37
  • 2
    $\begingroup$ I computed the determinant $\Delta(3)$ with a variable $x$ replacing $\xi$ and it can be factorized; it gives $x(x+1)(x-1)^3$. Maybe you can get a simple expression in general, using a Mathematica or any math software. $\endgroup$
    – efs
    Jun 23, 2017 at 16:55
  • 8
    $\begingroup$ Maybe just a coincidence, but still :$ \vert\Delta(2)\vert=2^{2/2} $ , $ \vert\Delta(3)\vert=3^{3/2} $ , $ \vert\Delta(4)\vert=4^{4/2} $ , so you can try to check whether $ \vert\Delta(n)\vert=n^{n/2} $ or not. $\endgroup$ Jun 23, 2017 at 17:38
  • 3
    $\begingroup$ This is all very nice, but I am really amazed by how @SylvainJULIEN got his heuristic out of a three experiments datum. $\endgroup$
    – Uri Bader
    Jun 24, 2017 at 11:36
  • 2
    $\begingroup$ Thank you very much but there's no magic behind this, it's just a matter a familiarity with numbers. $\endgroup$ Jun 24, 2017 at 12:00

5 Answers 5

35
$\begingroup$

Using the earlier responses and comments, I confirm the formula suggested by Neil Strickland: $$\Delta(d)=d^{d/2}i^{m(d)}\qquad\text{with}\qquad m(d): = 1 + d(7-d)/2\in\mathbb{Z}.$$ Consider the $d\times d$ Vandermonde matrix $$\Phi(d):=(\xi^{ij})_{0\leq i,j \leq d-1}.$$ Subtracting the first column from each other column, we get a matrix with first row equal to $(1,0,\dots,0)$ and lower right $(d-1)\times(d-1)$ block equal to the OP's matrix. Therefore, $$\Delta(d)=\det\Phi(d).$$ It is straightforward to check that $\Phi(d)^\ast\cdot\Phi(d)$ equals $d$ times the identity matrix, therefore $$ |\det\Phi(d)|^2=d^d.$$ In other words, $|\det\Phi(d)|=d^{d/2}$, and we are left with determining $$\frac{\det\Phi(d)}{|\det\Phi(d)|}=\prod_{0\leq i<j\leq d-1}\frac{\xi^j-\xi^i}{|\xi^j-\xi^i|}.$$ Let me use the notation $e(t):=e^{2\pi it}$, familiar from analytic number theory. Then we see that $$\xi^j-\xi^i=e\left(\frac{j}{d}\right)-e\left(\frac{i}{d}\right) =e\left(\frac{i+j}{2d}\right)\left(e\left(\frac{j-i}{2d}\right)-e\left(\frac{i-j}{2d}\right)\right).$$ On the right hand side, $0<\frac{j-i}{2d}<\frac{1}{2}$, hence $e\left(\frac{j-i}{2d}\right)$ lies in the upper half-plane. As a result, $$\frac{\xi^j-\xi^i}{|\xi^j-\xi^i|}=e\left(\frac{i+j}{2d}\right)i.$$ We need to calculate the product of the right hand side over the $\binom{d}{2}$ pairs $0\leq i<j\leq d-1$. By symmetry (or by brute-force calculation), the average of $i+j$ equals $d-1$, whence $$\prod_{0\leq i<j\leq d-1}\frac{\xi^j-\xi^i}{|\xi^j-\xi^i|}=\left(e\left(\frac{d-1}{2d}\right)i\right)^{\binom{d}{2}}=e\left(\left(\frac{d-1}{2d}+\frac{1}{4}\right)\binom{d}{2}\right).$$ We calculate $$\left(\frac{d-1}{2d}+\frac{1}{4}\right)\binom{d}{2}=\frac{(3d-2)(d-1)}{8},$$ therefore in the end $$\Delta(d)=d^{d/2}i^{n(d)}\qquad\text{with}\qquad n(d):=(3d-2)(d-1)/2\in\mathbb{Z}.$$ This agrees with Neil Strickland's formula, upon noting that $m(d)\equiv n(d)\pmod{4}$, i.e., $$2+d(7-d)\equiv (3d-2)(d-1)\pmod{8}.$$

Added 1. As Alexey Ustinov remarked, $\Phi(d)$ is known as a Schur matrix. As Carlitz wrote in his 1959 paper, "this matrix is familiar in connection with Schur's derivation of the value of Gauss's sum". In fact, on page 295 of this paper, Carlitz uses the known value of Gauss's sum to find the eigenvalues of this matrix (which are all of the form $\pm\sqrt{d}$ and $\pm i\sqrt{d}$, hence one only needs to find the 4 multiplicities). This can be regarded as a refinement and an alternate proof of the above result, since the product of the eigenvalues is the determinant.

Added 2. Carlitz referred to Landau's Vorlesungen, whose relevant part appeared in English as Landau: Elementary Number Theory (Chelsea, 1958). So I looked up this translation, and to my surprise on pages 211-212 I found essentially the same calculation as above. In fact all this is in Schur's 1921 paper, thanks to Alexey Ustinov for locating it for me (alternative link here). As Landau explains (following Schur), the determinant calculation leads to an evaluation of Gauss's sum, at least for odd $d$. The point is that one can figure out the 4 eigenvalue multiplicities from the determinant, and hence one obtains the formula for the trace of $\Phi(d)$ as well. However, this trace is nothing but Gauss's sum!

Added 3. For a more recent treatment of Schur's evaluation of the Gauss sum, see Section 6.3 in Rose: A course in number theory (2nd ed., Oxford University Press, 1994).

$\endgroup$
12
  • 3
    $\begingroup$ May I mention that essentially the same calculation is in section 3.1 of arxiv.org/abs/1304.7202. $\endgroup$ Jun 24, 2017 at 2:25
  • 4
    $\begingroup$ $\Phi$ is known as Schur Matrix mathworld.wolfram.com/SchurMatrix.html $\endgroup$ Jun 24, 2017 at 3:08
  • 2
    $\begingroup$ @AlexeyUstinov: Thanks for your valuable remark, which led to the "Added" section in my response. $\endgroup$
    – GH from MO
    Jun 24, 2017 at 3:49
  • 5
    $\begingroup$ Original Schur's article is here eudml.org/doc/59098 $\endgroup$ Jun 24, 2017 at 4:13
  • 2
    $\begingroup$ Great! I'm glad to learn of this. Thank you Alexey and GH. $\endgroup$ Jun 24, 2017 at 5:03
17
$\begingroup$

Numerical experiment (as far as $d=50$) makes it clear that $\Delta(d)=d^{d/2}i^{m_d}$ where $$ m_d = 1 + d(7-d)/2 \in\mathbb{Z}. $$ I haven't tried to find a proof, however.

$\endgroup$
4
  • $\begingroup$ The matrix determinant is equivalent, as Federico mentioned above, to a scalar t times the determinant of a modified Vandermonde with first column all 1's and remaining columns the ijth power of the root of unity. If you can come up with a proof or expression for t(d), you might get a proof of the general result. Gerhard "T For Two Or Three" Paseman, 2017.06.23. $\endgroup$ Jun 23, 2017 at 19:08
  • 3
    $\begingroup$ Amazing. Did you use the OEIS, or are the origins of this formula voodoo-theoretic? $\endgroup$ Jun 23, 2017 at 22:51
  • $\begingroup$ I confirmed your formula below. $\endgroup$
    – GH from MO
    Jun 23, 2017 at 23:00
  • 2
    $\begingroup$ @ViditNanda The absolute value was conjectured by SylvainJULIEN, and easily verified numerically. It is also easily visible numerically that $\Delta(d)=d^{d/2}i_{m_d}$ for some $m_d$ which only matters mod $4$ and which you can tabulate. You then observe that $m_{d+8}=m_{7-d}=m_d\pmod{4}$, and from there you only need a little guesswork. $\endgroup$ Jun 24, 2017 at 14:16
10
$\begingroup$

Partial answer, to expand on my suggestion as requested by OP: let $\Phi=(\xi^{ij})_{0\leq i,j \leq d-1}$ be the FFT matrix; in particular, its first row and column contain all ones. Let $$ L = \begin{bmatrix}1 \\ -1 & 1\\ -1 && 1 \\ \vdots & & & \ddots \\ -1 & &&&1\end{bmatrix} $$ be the elementary matrix that does one step of Gaussian elimination. One can check that $$ L\Phi = \begin{bmatrix}1 & 1 & \dots & 1\\ 0\\\vdots & & M\\0\end{bmatrix}, $$ where $M$ is the matrix whose determinant you wish to compute. By comparing determinants, $\det M = \det \Phi$. The Vandermonde determinant formula gives $$ \det \Phi = \prod_{0\leq i<j < d} (\xi^i-\xi^j). $$ So the problem can be reduced to finding a closed formula for this product. I don't have an immediate solution but it looks like a manageable problem.

$\endgroup$
2
  • 2
    $\begingroup$ note that for fixed $i$ the product $\prod_{j\ne i} (\xi^i-\xi^j)$ is the derivative of the polynomial $z^n-1$ at $z=\xi^i$, which equals $n\xi^{-i}$. Multiplying by all $i$ gives you the value of the square of $\det \Phi$. And it is routine to find the argument, since we know the arguments of all brackets. $\endgroup$ Jun 23, 2017 at 20:04
  • 2
    $\begingroup$ @FedorPetrov Good point. Another quick way to find the absolute value of the determinant is via the relation $\Phi^*\Phi=nI$. $\endgroup$ Jun 23, 2017 at 20:09
8
$\begingroup$

(Too long for a comment) Replacing $\xi$ with a variable $x$, Mathematica gives the following:

\begin{align*} \Delta(2)&=-1+x\\ \Delta(3)&=(-1+x)^3 x (1+x)\\ \Delta(4)&=(-1+x)^6 x^4 (1+x)^2 \left(1+x+x^2\right)\\ \Delta(5)&=(-1+x)^{10} x^{10} (1+x)^4 \left(1+x^2\right) \left(1+x+x^2\right)^2\\ \Delta(6)&=(-1+x)^{15} x^{20} (1+x)^6 \left(1+x^2\right)^2 \left(1+x+x^2\right)^3 \left(1+x+x^2+x^3+x^4\right) \end{align*} etc...

There is a nice pattern: for $d\ge3$, $\Delta(d)$ contains as factors exactly the cyclotomic polynomials of degree 1 to $d-1$, and $x$, raised to some powers.

Edit: I checked up to $d=12$ and, as Benjamin remarks, the exponents seems to be:

I searched in the OEIS for other exponent sequences, but it returns a lot of possibilities. For example, the exponents over $1+x$ go like this: 1,2,4,6,9,12,16,20,25,30,..., and the OEIS gives 16 results: https://oeis.org/search?q=1%2c2%2c4%2c6%2c9%2c12%2c16%2c20%2c25%2c30

Another edit: Problem solved, see at the end of T. Amdeberhan's answer.

$\endgroup$
3
  • 1
    $\begingroup$ Is it clear what the exponents are? E.g., 1, 3, 6, 10, 15, ... are triangular numbers, then 0, 1, 4, 10, 20, ... are triangular pyramidal numbers... $\endgroup$ Jun 24, 2017 at 20:59
  • 1
    $\begingroup$ Interesting. I will check that with large $d$ when I have some time. $\endgroup$
    – efs
    Jun 24, 2017 at 21:11
  • $\begingroup$ @EFinat-S: see the answer given below. $\endgroup$
    – Lewi_Sol
    Jun 24, 2017 at 22:08
5
$\begingroup$

Let $\Phi=(\xi^{ij})_{0\leq i,j \leq d-1}$. Then $\det\Phi=\prod_{0\leq i<j < d} (\xi^i-\xi^j)=(-1)^{\binom{d}2}\prod_{0\leq i<j < d} (\xi^j-\xi^i)$. So, \begin{align} \prod_{0\leq i<j < d} (\xi^j-\xi^i)^2 &=\det\begin{bmatrix}1&1 &\dots &1 \\ x_0&x_1&\dots&x_{d-1} \\ \vdots&\vdots&\dots&\vdots \\ x_0^{d-1}&x_1^{d-1}&\dots&x_{d-1}^{d-1} \end{bmatrix} \det\begin{bmatrix}1&x_0 &\dots &x_0^{d-1} \\ 1&x_1&\dots&x_1^{d-1} \\ \vdots&\vdots&\dots&\vdots \\ 1&x_{d-1}&\dots&x_{d-1}^{d-1} \end{bmatrix} \\ &=\det\begin{bmatrix}t_0&t_1 &\dots &t_{d-1} \\ t_1&t_2&\dots&t_d \\ \vdots&\vdots&\dots&\vdots \\ t_{d-1}&t_d&\dots&t_{2(d-1)}\end{bmatrix}; \end{align} where $x_k=\xi^k$ and $t_k=x_0^k+x_1^k+\cdots+x_{d-1}^k$. Notice that $t_k=0$ unless $k$ is a multiple $d$, in which case it is equal to $d$. Therefore, $$\prod_{0\leq i<j < d} (\xi^j-\xi^i)^2 =d^d\cdot\det \begin{bmatrix}1&0&0&\dots&0&0 \\ 0&0&0&\dots&0&1 \\ 0&0&0&\dots&1&0 \\ \vdots&\vdots&\vdots&\dots&\vdots&\vdots \\ 0&1&0&\dots&0&0\end{bmatrix}=d^d(-1)^{\binom{d-1}2}.$$ We gather that $$\det\Phi=(-1)^{\binom{d}2}\cdot d^{\frac{d}2}\cdot i^{\binom{d-1}2} =d^{\frac{d}2}\cdot i^{\frac{(3d-2)(d-1)}2}.$$

A couple of noteworthy facts: if $V=\prod_{0\leq i<j < d} (\xi^j-\xi^i)$ denote the Vandermonde determinant, then

$V^2$ is the discriminant of the polynomial $f(z)=z^d-1$;

$V^2$ is a symmetric polynomial and when expanded in elementary polynomials basis then only $e_d(\xi_0,\dots,\xi_{d-1})$ survives.

By the way, in general, computing the coefficients of even-powers of the Vandermonde's determinant $V(y_1,\dots,y_n)$ symmetric polynomials basis is a difficult and big sport in mathematics and physics.

UPDATE. This is in response to EFinat-S's quest on replacing $\xi$ by an indeterminate $x$. The determinant is just $$\Delta(d)=\det\left[x^{ij}-1\right]_{i,j}^{1,d} =\prod_{0\leq i<j\leq d}\left(x^j-x^i\right).$$

POSTSCRIPT. We can generalize the determinant evaluation as follows. Start with the Vandermonde $$\prod_{i<j}^{\pmb{0,d-1}}(y_j-y_i)=\det\begin{bmatrix}1&y_0 &\dots &y_0^{d-1} \\ 1&y_1&\dots&y_1^{d-1} \\ \vdots&\vdots&\dots&\vdots \\ 1&y_{d-1}&\dots&y_{d-1}^{d-1} \end{bmatrix},$$ then choose $y_0=1$ and subtract the first column from the rest to get $$\det\begin{bmatrix}1&y_0-1 &\dots &y_0^{d-1}-1 \\ 1&y_1-1&\dots&y_1^{d-1}-1 \\ \vdots&\vdots&\dots&\vdots \\ 1&y_{d-1}-1&\dots&y_{d-1}^{d-1}-1 \end{bmatrix} =\det\begin{bmatrix}1&y_1-1 &\dots &y_1^{d-1}-1 \\ 1&y_2-1&\dots&y_2^{d-1}-1 \\ \vdots&\vdots&\dots&\vdots \\ 1&y_{d-1}-1&\dots&y_{d-1}^{d-1}-1 \end{bmatrix}.$$ Consequently, $$\det\begin{bmatrix}1&y_1-1 &\dots &y_1^{d-1}-1 \\ 1&y_2-1&\dots&y_2^{d-1}-1 \\ \vdots&\vdots&\dots&\vdots \\ 1&y_{d-1}-1&\dots&y_{d-1}^{d-1}-1 \end{bmatrix} =\prod_{k=1}^{d-1}(y_k-1)\cdot\prod_{i<j}^{\pmb{1,d-1}}(y_j-y_i).$$ The latter determinant is in the form of your question, with $y_j=\xi^j$.

$\endgroup$
3
  • 1
    $\begingroup$ You say $\det \Phi = (-1)^{\binom{d}{2}} \left( d^d (-1)^{\binom{d-1}{2}} \right)^{1/2} = (-1)^{\binom{d}{2}} d^{\frac{d}{2}} i^{\binom{d-1}{2}}$. Is it obvious that we get $i$ instead of $-i$ at the end? Or do we need something like the accepted answer's argument (pun intended)? $\endgroup$ Jun 24, 2017 at 17:55
  • $\begingroup$ Your first line should be corrected as $\det\Phi=\prod_{0\leq i<j < d} (\xi^j-\xi^i)$. Also, Zach Teitler is right: distinguishing between $\pm i$ is subtle here, and it is pretty much the same problem as evaluating the Gauss sum precisely (not only up to $\pm$ sign which is an easier task). The point is that $(\det\Phi)^2$ has two square-roots, and you need to pin down which one is $\det\Phi$. $\endgroup$
    – GH from MO
    Jun 24, 2017 at 19:08
  • $\begingroup$ Of course. I should read more carefully the other answers before posting. Thanks for the response. (I was entertaining myself with this determinant in Mathematica while finishing some pending bureaucratic work in the computer.) $\endgroup$
    – efs
    Jun 24, 2017 at 22:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.