Skip to main content
2 of 2
added 494 characters in body
Gjergji Zaimi
  • 85.6k
  • 4
  • 236
  • 402

I'll keep the version where we look at $$D(w,v)=\det\left(I + Z+ \ldots + Z^{w-1}-Z^{w-1}\mathrm{diag}(\mathbf{v})\right)$$ and ask when is $D(w,v)=1$?

In order to give a complete answer to both conjectures we first introduce the quiver $Q_{w,v}$ defined on the vertices $\{S_1,S_2,\dots,S_n\}$ with edges $S_i\to S_{i+w-v_i}$. Here by $v_i$ we are denoting the $i$-th component of $\mathbf v$. If we have a cycle $C$ on vertices $\{S_{i_1},\dots,S_{i_r}\}$ we define the weight of $C$ to be $$\omega(C)=\frac{rw-\sum_{j=1}^r v_i}{n}.$$ Notice that each connected component of $Q_{w,v}$ has a unique cycle, because each vertex has outdegree 1.

Theorem: If $Q_{w,v}$ is connected then $D(w,v)$ is equal to the weight of the unique cycle in $Q_{w,v}$, otherwise we have $D(w,v)=0$.

Proof: Let's deal with the case where $Q_{w,v}$ is disconnected first. If $C_1,C_2$ are two cycles then the sum of all rows indexed by the vertices of $C_1$ is equal to $\frac{\omega(C_1)}{\omega(C_2)}$ times the sum of all rows corresponding to the vertices of $C_2$. This gives a linear relation among the rows, therefore $D(w,v)=0$.

If $Q_{w,v}$ is connected then we can argue as follows. If we have vertices $S_{i_1}\rightarrow S_{i_3}\leftarrow S_{i_2}$, then we must have $v_{i_1}=0, v_{i_2}=1$ or $v_{i_1}=1,v_{i_2}=0$. Without loss of generality we are in the first case and we can subtract the $i_1$-th row from the $i_2$-th row and obtain a row with one 1, and all 0's. This shows that $D(w,v)$ is equal to its $(i_2,i_2)$ minor. You can continue reducing the matrix this way until the quiver of the matrix becomes a simple cycle. It is easy to see that when passing to a minor at each step doesn't change the weight of the cycle. At the end you will be left with a matrix of the form $I+z+\cdots+z^{\omega(C)-1}$, where $z$ is a shift matrix, and this matrix has determinant $\omega(C)$. $\blacksquare$


Corollary 1: When $n$ is even we have $\max G_n=\frac{n+2}{2}$, and this is achieved by $\frac{3^{\frac{n}{2}-1}+1}{2}$ vectors $\mathbf v$ up to cyclic shift.

Proof: Since a cycle will have at least two vertices we get $n\geq 2(w-1)\implies w\le \frac{n+2}{2}$. For this to be achieved we need two vertices to satisfy $v_i=v_{i+n/2}=1$. Because cyclic shifts of $\mathbf v$ are equivalent, we can assume that $v_{n/2}=v_n=1$. Now for each ordered pair $(v_i,v_{i+n/2})$ we have 3 possibilities since if it was $(1,1)$ it would give a new cycle in the quiver $Q_{w,v}$ which is not possible, so it has to be one of $(0,0),(0,1),(1,0)$. In total we get $3^{n/2}$ possibilities for the vector $v$. It is possible to show that all of these work because the associated quiver is connected. However each vector except for $\mathbf v=(0,\dots,0,1,0,\dots,0,1)$ is counted twice (by $n/2$ rotation), giving us a final count of $\frac{3^{\frac{n}{2}-1}+1}{2}$. $\blacksquare$

Corollary 2: When $n$ is odd we have $\max G_n=\frac{n+1}{2}$, and this is achieved by $n-1$ vectors $\mathbf v$ up to cyclic shift.

Proof: To get a cycle of weight 1 we need $v_i=1,v_{i+\frac{n-1}{2}}=0$, for some $i$. When we order the coordinates as $v_i,v_{i-\frac{n-1}{2}}, v_{i+1}, v_{i-\frac{n-3}{2}},\dots$ we see that the only possibility is to have a bunch of 1's followed by a bunch of 0's. The number of 1's can be anything from $1$ to $n-1$, each giving rise to a unique valid $\mathbf v$ up to cyclic shift. $\blacksquare$

Corollary 3: The allowed values in $G_n$ are $w=1+\lfloor \frac{n}{r}\rfloor$ where $2\le r\le n$, together with the values $w=\frac{n}{r}$, where $2\le r\le n$ and $r$ divides $n$.

Proof: Suppose the unique cycle has $r$ vertices, and $r_1$ of them have $v_i=1$. Then since the weight of the cycle is 1, we get $n=rw-r_1$ and the conclusion follows. This shows in particular that the guess $G_n=\{2,3,\dots, 1+\lfloor n/2\rfloor \}$ is wrong for large enough $n$. $\blacksquare$

Gjergji Zaimi
  • 85.6k
  • 4
  • 236
  • 402