7
$\begingroup$

This is a continuation of Classification of algebras of finite global dimension via determinants of certain 0-1-matrices but this time with a concrete conjecture and using the simplification suggested by user esg to make the problem more compact.

Let $n \geq 4$ and $w \in \{3,4,...,n-1 \}$. Let $Z$ be the matrix of the cyclic shift (the companion matrix of $X^n-1$), and for non-zero $\mathbf{v}\in \{0,1\}^n$ let $\mathrm{diag}(\mathbf{v})$ be the diagonal matrix with $\mathbf{v}$ on the diagonal, and $M_\mathbf{v}:=I + Z+ \ldots + Z^{w-1}-\mathrm{diag}(\mathbf{v})$.
For fixed $n$, call the tuple $(w,v)$ perfect in case $\det(M_\mathbf{v})=(-1)^{(w-1)(n-1)}$. (here I used the reformulation obtained by user esg for my problem. I refer to the previous thread for a motivation. Roughly stated, perfect pairs correspond to certain algebras with finite global dimension. )

Define $G_n := \{ w \in \{3,4,...,n-1\} | $there exists a nonzero $\mathbf{v}\in \{0,1\}^n$ with $(w,v)$ perfect $\}$.

It is best to picture the $v$ as two-colored necklaces (with colours corresponding to 1 and 0), so a cyclic shift just means rotating the necklace.

It is an interesting question what the set $G_n$ is explicitly but my first guess was wrong and it seems that $G_n$ is complicated to describe for large $n$.

But here are two conjectures that would be nice in case they are true:

Conjecture 1: Maximum($G_n$)=$\frac{n+2}{2}$ in case $n$ is even and Maximum($G_n$)=$\frac{n+1}{2}$ in case $n$ is odd.

Conjecture 2: a) For $n$ even the number of perfect tuples $(w,v)$ with $w=(n+2)/2$ is equal to $\frac{3^{n/2-1}+1}{2}$ when we identify two tuples $(w,v_1)$ and $(w,v_2)$ when $v_1$ is a cyclic shift of $v_2$.

b) For $n$ odd the number of perfect tuples $(w,v)$ with $w=(n+1)/2$ is equal to $n-1$ when we identify two tuples $(w,v_1)$ and $(w,v_2)$ when $v_1$ is a cyclic shift of $v_2$.

The conjectures are tested with the computer for $n \leq 20$.

Here two examples:

For $n=13$ and $w=7$, the $v$ up to cyclic shift with $(w,v)$ perfect are:

[ [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ],

[ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1 ],

[ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1 ],

[ 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1 ],

[ 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1 ],

[ 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1 ],

[ 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1 ],

[ 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1 ],

[ 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1 ],

[ 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 ],

[ 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 ],

[ 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ] ]

For $n=8$ and $w=5$, the perfect $(w,v)$ up to cyclic shifts are:

[ [ 0, 0, 0, 1, 0, 0, 0, 1 ],

[ 0, 0, 0, 1, 0, 0, 1, 1 ],

[ 0, 0, 0, 1, 0, 1, 0, 1 ],

[ 0, 0, 0, 1, 0, 1, 1, 1 ],

[ 0, 0, 0, 1, 1, 0, 0, 1 ],

[ 0, 0, 0, 1, 1, 0, 1, 1 ],

[ 0, 0, 0, 1, 1, 1, 0, 1 ],

[ 0, 0, 0, 1, 1, 1, 1, 1 ],

[ 0, 0, 1, 0, 0, 1, 1, 1 ],

[ 0, 0, 1, 0, 1, 0, 1, 1 ],

[ 0, 0, 1, 0, 1, 1, 1, 1 ],

[ 0, 0, 1, 1, 0, 1, 0, 1 ],

[ 0, 0, 1, 1, 1, 1, 0, 1 ],

[ 0, 1, 0, 1, 1, 0, 1, 1 ] ]

edit: It might be also a good idea to think about conjecture 1 in terms of representation theory/homological algebra. Here is the non-elementary formulation of conjecture 1:

Let $A$ be a selfinjective (connected) Nakayama algebra with $n$ simple modules and Loewy length $w$ with $(n+2)/2 < w<n$. Then a generator $M$ with every non-projective indecomposable summand being simple has the property that $End_A(M)$ has infinite global dimension.

(equivalently, one can look at generators $M$ with every non-projective indecomposable summand being a radical of an indecomposable projective module).

$\endgroup$
4
  • 1
    $\begingroup$ It might be useful to consider $M(t)=1+tZ+\cdots+(tZ)^{w-1}-D$. The determinant of $M(t)(1-tZ)=(1-D)+tDZ-t^wZ^w$ should have few nonzero terms. $\endgroup$
    – MTyson
    Mar 22, 2019 at 18:27
  • $\begingroup$ Concerning conjecture 1: is it obvious or easy that the given maxima can be reached? Or is it part of the problem? $\endgroup$
    – esg
    Mar 26, 2019 at 20:24
  • $\begingroup$ @esg Yes, I think that this is easy. In fact the perfect $(w,v)$ for $n$ odd and $w=(n+1)/2$ seem to have a very nice pattern, but for $n$ even I have not figured out what the pattern might be yet. But the pattern is probably also very nice since the sequence oeis.org/A007051 has many nice interpretations. $\endgroup$
    – Mare
    Mar 26, 2019 at 21:07
  • $\begingroup$ For $n$ odd and $w=(n+1)/2$ one can take $v=(0,0,0....,0,1)$ and for $n$ even and $w=(n+2)/2$ one can take $v$ with exactly two ones in position $n/2$ and $n$. $\endgroup$
    – Mare
    Mar 26, 2019 at 21:26

1 Answer 1

6
+100
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ Small correction to Thm. 1 (I think): $\det(I+Z+\ldots+Z^{\omega(C)-1})$ will be $0$ if $1<\gcd(\omega(C),n)<n$ (so that you can get determinant $0$ also in the connected case). $\endgroup$
    – esg
    Mar 31, 2019 at 16:52
  • $\begingroup$ @esg: If the gcd is greater than 1, then there are multiple cycles in the quiver of that matrix. $\endgroup$ Mar 31, 2019 at 17:13
  • 2
    $\begingroup$ Ok, thanks (sorry, I should have noticed that). An amazing solution! $\endgroup$
    – esg
    Apr 1, 2019 at 16:23

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.