4
$\begingroup$

$\newcommand{\M}{\mathcal{M}}$Recently I encountered a certain class of matrices whose determinants behave in an interesting manner. Define $\M(n,k)$ for positive integers $n,k$ with $k\leq n$ to be the real $n\times n$ matrix with all $1$s on the diagonal, all $1$s for $k-1$ entries to the right of the diagonal on each row, and $0$s everywhere else. Note that if there are less than $k-1$ entries to the right of the diagonal, then the $1$s carry over to the leftmost columns. For example: $$\M(4,2)=\begin{bmatrix}1&1&0&0\\0&1&1&0\\0&0&1&1\\1&0&0&1\end{bmatrix}\quad\text{and}\quad\M(3,1)=\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}.$$

At first, I believed that $\M(n,k)$ would always be nonsingular when $k<n$, but this turned out to be false. The smallest example where this conjecuture fails is $\M(4,2)$, whose determinant is $0$. After even more numerical testing I have been led to believe the following new conjecture:

The determinant $\det\M(n,k)$ is $0$ if and only if $\gcd(n,k)>1$. If $n,k$ are coprime, then $\det\M(n,k)=k$.

I have tested for all $k\leq n$ up to $n=9$ with the help of a computer without any counterexamples. Does anyone have an idea how this conjecture might be proven?


Here are some partial results. It is trivial that $\det\M(n,k)$ is zero when $k=0$ or $n$, and that it is $1$ when $k=1$. I can prove the result when $k=2$ as well: Let $U(n)$ be the $n\times n$ matrix with all entries $0$ except a $1$ at the bottom leftmost corner. Then, we have the recurrence relation $$\det\M(n,2)=\det\big(\M(n-1,2)-U(n-1)\big)+(-1)^{n+1}\det\big(\M(n-1,2)^t-U(n-1)^t\big)$$ which of course simplifies to $$\det\M(n,2)=(1+(-1)^{n+1})\det\big(\M(n-1,2)-U(n-1)\big).$$ Upon verifying $\det\M(2,2)=0$, it's clear that this proves the conclusion for $k=2$ if we assume that $\det\big(\M(n-1,2)-U(n-1)\big)=1$. Call the LHS $x(n-1)$. It is easy to compute that $x(2)=1$, from which it follows by induction $x(n)=1$ for all $n$, since $x(n+1)=x(n)$.


Unfortunately, I am at a complete loss in any of the cases other than $k=0,1,2,n$. It seems like (for sufficiently large $n$) as $k$ increases from $3$ until $\lfloor n/2\rfloor$, the proof going by the same thinking as my proof for $k=2$ would get increasingly complicated until it becomes hopeless to even attempt. (I could be wrong, of course.) Not to mention the general case for any positive integer $n$.

Does anyone have an idea how to attack the general problem? Thanks in advance!

$\endgroup$
  • 2
    $\begingroup$ Your matrix is a circulant matrix, its determinant equals to $\prod_{\ell=0}^{n-1} P(\omega^\ell)$ where $\omega$ is the $n^{th}$ of unity and $P(x) = 1 + x + \cdots + x^{k-1}$. $\endgroup$ – achille hui Apr 5 at 0:37
  • $\begingroup$ @achillehui Thank you for the great hint! $\endgroup$ – YiFan Apr 5 at 1:53
2
$\begingroup$

$\newcommand{\M}{\mathcal{M}}$Thanks to @achillehui's suggestion, I am able to prove the conjecture, and I present the proofs below. For any $n\times n$ circulant matrix $C$ with column vectors being the permutations of a certain vector $c=(c_0,c_1,\dots,c_{n-1})^T$, and with the associated polynomial $p(x)=c_0+c_1x+\dots+c_{n-1}x^{n-1}$, the following is known.

The determinant of $C$ is given by $\displaystyle\prod_{j=0}^{n-1}p(\zeta_n^j)$, where $\zeta_n:=\exp(2\pi i/n)$ is the primitive $n$th root of unity.

The matrices $\M(n,k)$ are circulant, with associated polynomial $p(x)=1+x+\dots+x^{k-1}$. Note that whenever $x\neq 1$, we have $p(x)=(x^k-1)/(x-1)$, so we may write $$\det\M(n,k)=\prod_{j=0}^{n-1}p(\zeta_n^j)=p(1)\prod_{j=1}^{n-1}\frac{\zeta_n^{jk}-1}{\zeta_n^j-1}.$$ In the case where $\gcd(n,k)=:d>1$, we know that $\zeta_n^k$ is no longer a primitive $n$th root of unity, but it is a primitve $(n/d)$th root of unity. Since $d>1$, the integer $n/d$ lies in the set $\{1,2,\dots,n-1\}$ from which $j$ takes values in the product, so there is a term in the product where $j=n/d$. For this term, the numerator is $\zeta_n^{jk}-1=\zeta_{n/d}^{n/d}-1=0$, so that the whole product is $0$ and the determiant is $0$. Conversely, when $d=1$, $\zeta_n^k$ will always be a primitive $n$th root of unity, and their $j$th powers will never be $1$ (for $1\leq j\leq n-1$). Hence the product is nonzero.

The stronger conjecture that $\det\M(n,k)=k$ when $\gcd(n,k)=1$ can be proven in this way as well. It is trivial that $p(1)=k$, so it suffices to show the product $\prod(\zeta_n^{jk}-1)/(\zeta_n^j-1)$ is $1$. The reason this is true is because of cancellation. The element $k$ in the additive group $\mathbb Z/n\mathbb Z$ (which is isomorphic to the multiplicative group of roots of unity) always generates the group whenever $n,k$ are coprime. Furthermore, each element is generated in a unique way. Therefore, as $j$ takes all nonzero values in $\mathbb Z/n\mathbb Z$, every element is represented exactly once, so the cancellation is perfect, proving the result.

$\endgroup$
0
$\begingroup$

If you use row operations, you can see where the periodicity comes in. As an example take $M(5,3)$; subtract the first row from the two bottom ones, then add the second row, etc.:

$$\begin{pmatrix}1&1&1&0&0\\0&1&1&1&0\\0&0&1&1&1\\{\color{red}1}&0&0&1&1\\{\color{red}1}&{\color{red}1}&0&0&1\end{pmatrix}\mapsto\begin{pmatrix}1&1&1&0&0\\0&1&1&1&0\\0&0&1&1&1\\0&{\color{red}-\color{red}1}&{\color{red}-\color{red}1}&1&1\\0&0&\color{red}-\color{red}1&0&1\end{pmatrix}\mapsto\begin{pmatrix}1&1&1&0&0\\0&1&1&1&0\\0&0&1&1&1\\0&0&0&2&1\\0&0&-1&0&1\end{pmatrix}$$

Let us just track the $1$s in the lower left corner as you perform row subtraction or addition. You'll see that the triangle of $1$s moves right with a period of $k$ as seen below (omitting the $0$s):

$$k=2,\qquad 1\mapsto\quad-1\quad\mapsto 1$$ $$k=3,\qquad \begin{matrix}1\\1&1\end{matrix}\quad\mapsto\quad \begin{matrix}-1&-1\\&-1\end{matrix}\quad\mapsto\quad\begin{matrix}&1\\-1\end{matrix}\quad\mapsto\quad\begin{matrix}1\\1&1\end{matrix}$$

$$k=4,\qquad\begin{matrix}1&&\\1&1&\\1&1&1\end{matrix}\quad\mapsto\quad\begin{matrix}-1&-1&-1\\&-1&-1\\&&-1\end{matrix}\quad\mapsto\quad\begin{matrix}&&1\\-1&-1\\&-1\end{matrix}\quad\mapsto\quad\begin{matrix}&&1\\&1&1\\-1\end{matrix}\quad\mapsto\quad\begin{matrix}1\\1&1\\1&1&1\end{matrix}$$

When the $1$s have moved by $k$ steps, they leave a matrix of $0$s behind. Since $\det\begin{pmatrix}A&B\\O&C\end{pmatrix}=\det A\det C$, and since the upper left matrix $A$ has determinant 1, it follows that $\det M(n,k)=\det M(n-k,k)$. So what's left is to check what happens when this triangle of $1$s meets the rest of the matrix as it moves right. The end result is one of $M(k,k)$, $M(k+1,k)$,..., $M(2k-1,k)$. Clearly if $n$ is a multiple of $k$ we reach the matrix $M(k,k)$ of all $1$s which has determinant $0$. I believe you can take it from here.

$\endgroup$
  • 1
    $\begingroup$ Sorry, I'm afraid I don't understand what you're trying to say. What do you mean by "as you perform row subtraction or addition"? Which rows are added/subtracted from which others? I don't understand what your diagram is trying to say, nor to I get anything at all in the last paragraph. Maybe you want to rephrase it? $\endgroup$ – YiFan Apr 6 at 1:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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