Powers of matrices with all principal minors equal to 1

Definitions and the main result

Throughout this note, rings are commutative, associative and unital. For $n\in\mathbb{N}$, we set $[n]:=\{1,2,\ldots,n\}$.

If $A=(a_{i,j})_{i,j\in[n]}$ is an $n\times n$-matrix over a ring $R$ and if $S\subseteq[n]$, then $A_S$ denotes the principal submatrix of $A$ with row and column set $S$. That is, $A_S=\operatorname{sub}^{S}_{S}A$ in the notation of [2]. For instance,

The principal minors of an $n\times n$-matrix $A$ are its minors $\det A_S$ for all $S\subseteq[n]$. We use the convention that the empty determinant is $1$.

Problem B5 of the 2021 Putnam contest [1 Problem B5] asserts that if $A\in\mathbb{Z}^{n\times n}$ is an integer matrix whose all principal minors are odd, then all powers $A^m$ of $A$ have the same property. By reducing the matrix modulo $2$, this can be restated as follows: If $A\in(\mathbb{Z}/2)^{n\times n}$ is a matrix over the two-element field $\mathbb{Z}/2$ whose all principal minors equal $1$, then all its powers $A^m$ have the same property. This suggests a generalization to arbitrary commutative rings instead of $\mathbb{Z}/2$; however, this generalization was disproved in [2 §6] for $4\times4$-matrices over a certain finite ring.²

In this note, we shall show that this generalization is nevertheless true if we replace $\mathbb{Z}/2$ by any ring of the form $\mathbb{Z}/d$ with $d\in\mathbb{Z}$. More generally, it is true over every quotient $D/I$ whose kernel ideal $I$ is integrally closed in $D$. This includes quotients of Prüfer domains by arbitrary ideals and quotients of normal domains by principal ideals.

We introduce some terminology for the type of matrices we will study.

Note that the diagonal entries of an $n\times n$-matrix are its $1\times1$ principal minors. Hence, the diagonal entries of a 1-principled matrix are $1$.

Also, each 1-principled matrix $A$ has determinant $\det A=1$ (since $\det A=\det A_{[n]}$ is a principal minor of $A$), and thus is invertible (since a matrix with invertible determinant is invertible). Thus, its powers $A^m$ are defined for all integers $m$.

Our main result is the following theorem, which recovers Problem B5 of the 2021 Putnam contest when we take $D=\mathbb{Z}$ and $I=2\mathbb{Z}$ and $m\geq0$.

The notion of an integrally closed ideal will be recalled in § 4.

Our proof of Theorem 1.2 will be obtained by a combination of several results involving other properties of matrices. We shall introduce them one by one now.

Note that [2 Theorem 5.2] says that if $A$ is a 1-principled matrix and $m \in\mathbb{N}$, then $A^m$ is 1-diagonal.

The following simple proposition is an exercise in unfolding definitions:

Proof. $\Longrightarrow$: Assume that $A$ is 1-principled. Then, each diagonal entry $a_{i,i}$ of $A$ equals the principal $1 \times1$-minor $\det A_{\{i\}}$, which is 1 since $A$ is 1-principled. Thus, $A$ is 1-diagonal. Furthermore, for every $S \subseteq[n]$, we have $\prod_{i\in S} a_{i,i} = 1$ (since all factors $a_{i,i}$ of this product are 1, as we just saw) and $\det A_S = 1$ (since $A$ is 1-principled), so that $\det A_S = \prod_{i\in S} a_{i,i}$ (by comparing the preceding two equalities). This shows that $A$ is principled. Thus, we have proved that $A$ is 1-diagonal and principled.

$\Longleftarrow$: Assume that $A$ is 1-diagonal and principled. Then, for every $S \subseteq[n]$, we have $\det A_S = \prod_{i\in S} a_{i,i}$ (since $A$ is principled). But all the factors $a_{i,i}$ of the latter product are 1 (since $A$ is 1-diagonal), so this equality rewrites as $\det A_S = \prod_{i\in S} 1 = 1$. This shows that $A$ is 1-principled. $\square$

Our last two matrix properties rely on a simple combinatorial notion.

(c) We say that $A$ is 1-nullcyclic if $A$ is 1-diagonal and nullcyclic.

Example 1.8. If a matrix $A=(a_{i,j})_{i,j\in[n]}$ is triangular, then $A$ is nullcyclic. Indeed, any nontrivial cycle on $[n]$ has an arc $(i,j)$ with $i<j$ and an arc $(i,j)$ with $i>j$, and at least one of these arcs will satisfy $a_{i,j}=0$; thus, the $A$-weight of the cycle is $0$. Thus, if a matrix $A=(a_{i,j})_{i,j\in[n]}$ is unitriangular (i.e., triangular and satisfies $a_{i,i}=1$ for all $i\in[n]$), then $A$ is 1-nullcyclic. However, there are 1-nullcyclic matrices that are not unitriangular, such as

We then claim the following twin to Theorem 1.2 (but only for $m\ge0$, since the invertibility of $A$ is no longer guaranteed):

The proof of Theorem 1.9 relies on three independent results, all of which hold over any (commutative) ring: First, every nullcyclic matrix is principled (Proposition 2.1), although the converse does not always hold. Second, nullcyclic matrices are stable under powers (Proposition 2.3). Third, every nontrivial cycle’s $A$-weight is integral over the ideal generated by the principal-minor defects (i.e., the principal minors minus the corresponding products of diagonal entries) (Theorem 4.6). In the setting of Theorem 1.9, this forces these weights to belong to $I$, since $I$ is integrally closed.

The proof of Theorem 1.2 will reuse these auxiliary results, partly in modified form. Further results will be proved along the way. Figure 1a provides a map of most of the implications we will prove (for all $m\in\mathbb{N}$): A solid arc stands for an implication valid over every commutative ring. A dashed blue arc denotes an implication for matrices over a quotient $D/I$, where $I$ is an integrally closed ideal of a commutative ring $D$. Labels on the arcs signify where the respective implications are shown (the letters “P.” and “T.” stand for “Proposition” and “Theorem”, respectively; trivial implications are unlabelled). Some of the results on the 1-side actually hold for every $m\in\mathbb{Z}$, as their labels indicate.

After we prove all the results we have described, we shall discuss some examples of integrally closed ideals.

Remark 1.10. The condition of being 1-principled has previously appeared in toric topology. A result of Masuda and Panov [3 Lemma 3.3] (which they credit to Dobrinskaya) says that, over an integral domain, every 1-principled matrix is conjugate by a permutation matrix to an upper unitriangular matrix. Thus, over an integral domain, all its powers are 1-principled for this stronger structural reason. This triangularization does not extend to arbitrary rings with zero divisors; for example, the 1-principled matrix in Example 1.8 is not conjugate by a permutation matrix to a triangular matrix.

In the special case of the field $\mathbb{Z}/2$, Choi [4 §2.1] used the above triangularization to identify 1-principled $n \times n$-matrices with labeled acyclic digraphs on $n$ vertices: the correspondence sends a digraph to its adjacency matrix plus the identity matrix. This arose in the study of small covers over cubes.

There is also a Gaussian-elimination interpretation. Let $P$ be a permutation matrix, and let $\Delta_k$ denote the $k \times k$ leading principal minor of $P^{-1}AP$, with $\Delta_0 = 1$. The standard $LU$ criterion [5 Theorem 9.1] (easily generalized to arbitrary commutative rings, see [7 Proposition 4.3 (e)]) says that $P^{-1}AP$ has a unique factorization $LU$, where $L$ is lower unitriangular and $U$ is upper triangular with invertible entries on its diagonal, whenever all the $\Delta_k$ are invertible; moreover, the $k$-th diagonal entry of $U$ is $\Delta_k/\Delta_{k-1}$. Hence, if $A$ is 1-principled, then $P^{-1}AP$ certainly does have such a factorization, and moreover both $L$ and $U$ are unitriangular, for every $P$. Conversely, if such a unitriangular $LU$ factorization exists for every $P$, then all principal minors of $A$ are 1. Thus this property gives an equivalent description of 1-principled matrices, although this description is not useful for proving any of our claims.

Nullcyclic matrices

We begin with the theory of nullcyclic matrices.

Proof. Let $A = (a_{i,j})_{i,j \in[n]}$ be a nullcyclic $n \times n$-matrix. Let $S \subseteq[n]$. We expand

(where $\mathfrak{S}_S$ is the group of all permutations of $S$). The identity permutation $\operatorname{id} \in\mathfrak{S}_S$ contributes the addend

to the right-hand side of (1). The remaining addends on the right-hand side of (2.1) correspond to non-identity permutations $\pi \in \mathfrak{S}_S$. Every non-identity permutation $\pi \in \mathfrak{S}_S$ has at least one nontrivial cycle $(i_1, i_2, \ldots, i_k)$ in its cycle decomposition. The corresponding addend on the right-hand side of (2.1)` therefore contains, as a factor, the $A$-weight $a_{i_1,i_2}a_{i_2,i_3}\cdots a_{i_{k-1},i_k}a_{i_k,i_1}$ of this nontrivial cycle. This factor is 0, since $A$

::: is nullcyclic. Hence all non-identity addends on the right-hand side of (1) vanish, and so the equality (1) simplifies to

That is, $A$ is principled.

We shall use some basic graph theory (see, e.g., [9 Chapter 4]). Let $\overrightarrow{K}_n$ be the simple digraph (i.e., directed graph) with $n$ vertices $1,2,\ldots,n$ and $n^2$ arcs $(i,j)$ for all $i,j \in[n]$. What we called “cycles on $[n]$” above are exactly the cycles of $\overrightarrow{K}_n$ (considered up to cyclic rotation). The nontrivial cycles on $[n]$ are then the cycles of $\overrightarrow{K}_n$ having length $>1$. We make the following elementary observation about walks.

Proof. Delete all loops³ from the closed walk. Since the original walk is not stationary, some arcs remain upon this deletion. Starting at any remaining arc and following the walk cyclically, eventually a vertex is repeated. The part of the walk between the first occurrence of this vertex and its next occurrence is a closed walk with no repeated internal vertices. This closed walk is therefore a cycle, and moreover a nontrivial cycle (since all loops have been deleted).

Proof. Let $m \in\mathbb{N}$. The case $m=0$ is clear, since $A^0=I_n$. Assume $m>0$. Write the $n \times n$-matrix $A$ as $A=(a_{i,j})_{i,j\in[n]}$. We also use $B_{i,j}$ to refer to the $(i,j)$-th entry of any matrix $B$; thus, $A_{i,j}=a_{i,j}$ for all $i,j\in[n]$.

It is well-known that for any two vertices $i$ and $j$ of $\overrightarrow{K}_n$, we have⁴

Let us refer to the product $a_{i_0,i_1}a_{i_1,i_2}\cdots a_{i_{m-1},i_m}$ in this sum as the $A$-weight of the walk $i=i_0\to i_1\to\cdots\to i_m=j$. Thus, (2) says that

We must prove that $A^m$ is nullcyclic. In other words, we must prove that every nontrivial cycle on $[n]$ has $A^m$-weight 0. Let

be a nontrivial cycle on $[n]$, with length $k>1$. We must show that $w_{A^m}(C)=0$. Note that $i_1\ne i_2$ (by the definition of a cycle, since $k>1$). Set $i_{k+1}=i_1$ (that is, read the indices cyclically modulo $k$). Then,

(by (3), applied to $i_j$ and $i_{j+1}$ instead of $i$ and $j$). Expanding this product, we obtain a sum over all $k$-tuples $(W_1,W_2,\ldots,W_k)$ of length-$m$ walks from $i_j$ to $i_{j+1}$ for each $j\in[k]$. The addend corresponding to such a $k$-tuple is the product of the $A$-weights of all these walks $W_1,W_2,\ldots,W_k$; but this is, of course, the $A$-weight of the closed walk $W_1W_2\cdots W_k$ (of length $km$) obtained by concatenating these $k$ walks. This closed walk $W_1W_2\cdots W_k$ is not stationary (since $i_1\ne i_2$ are two distinct vertices on it). Hence it contains a nontrivial cycle $C'$ (by Lemma 2.2). The $A$-weight of this cycle $C'$ is 0 since $A$ is nullcyclic. Thus, the whole closed walk $W_1W_2\cdots W_k$ has $A$-weight 0 as well (since $C'$ is contained in $W_1W_2\cdots W_k$, and thus the $A$-weight of $W_1W_2\cdots W_k$ is a multiple of the $A$-weight of $C'$).

Thus, we have shown that $w_{A^m}(C)$ is a sum of $A$-weights of certain closed walks, but each of these closed walks has $A$-weight 0. Hence,

As explained above, this completes the proof.

Proof. The matrix $A^m$ is nullcyclic by Proposition 2.3, and therefore is principled by Proposition 2.1.

so that $J^2=0$. Now define the block matrices

Both $A$ and $B$ are unitriangular and thus 1-nullcyclic (by Example 1.8). However,

This common product is not nullcyclic, since the nontrivial cycle $(1,3)$ has $AB$-weight 1.

1-Nullcyclic matrices

The analogue of Proposition 2.1 for 1-nullcyclic matrices follows easily from Proposition 2.1:

Proof. Let $A$ be a 1-nullcyclic matrix. Then, $A$ is nullcyclic and thus principled (by Proposition 2.1). But $A$ is furthermore 1-diagonal (being 1-nullcyclic). Hence, $A$ is 1-principled (by Proposition 1.5). □

Next we derive the analogue of Proposition 2.3 for 1-nullcyclic matrices:

Proof. Let $m \in\mathbb{N}$. The case $m=0$ is again clear, since $A^0=I_n$. Assume $m>0$. We know from Proposition 2.3 that $A^m$ is nullcyclic; thus, it remains to show that $A^m$ is 1-diagonal. In other words, we must show that all diagonal entries of $A^m$ are 1.

Write the $n \times n$-matrix $A$ as $A=(a_{i,j})_{i,j\in[n]}$. We also use $B_{i,j}$ to refer to the $(i,j)$-th entry of any matrix $B$; thus, $A_{i,j}=a_{i,j}$ for all $i,j\in[n]$.

The matrix $A$ is 1-nullcyclic, hence 1-diagonal. That is, all diagonal entries of $A$ are 1: For each $i\in[n]$, we have

Fix $i\in[n]$. The equality (3) shows that $(A^m)_{i,i}$ is the sum of the $A$-weights of all length-$m$ walks from $i$ to $i$. The stationary walk $i=i\to i\to\cdots\to i=i$ contributes 1 to this sum, since its $A$-weight is $a_{i,i}a_{i,i}\cdots a_{i,i}=a_{i,i}^m=1$ (by (4)). Each of the other length-$m$ walks from $i$ to $i$ contains a nontrivial cycle by Lemma 2.2 (since it is a closed walk but not stationary). Since the latter cycle has $A$-weight $0$ (because $A$ is nullcyclic), we conclude that the walk that contains it must have $A$-weight $0$ as well (indeed, since $R$ is commutative, the $A$-weight of the cycle is a factor of the $A$-weight of the walk). Thus, $(A^m)_{i,i}$ is the sum of a single $1$ (corresponding to the stationary walk $i=i\to i\to\cdots\to i=i$) and a lot of $0$’s (coming from all the other walks). Therefore,

Forget that we fixed $i$. So we have proved (5) for each $i\in[n]$. In other words, all diagonal entries of $A^m$ are $1$. This completes the proof.

Remark 3.3. Alternatively, we could have proved Proposition 3.2 as follows: Proposition 3.1 shows that $A$ is 1-principled. Thus, [2 Theorem 5.2] (which says that any power of a 1-principled matrix is 1-diagonal) shows that $A^m$ is 1-diagonal. But Proposition 2.3 shows that $A^m$ is nullcyclic. Combining these two results, we conclude that $A^m$ is 1-nullcyclic.

We have shown in Proposition 3.2 that 1-nullcyclic matrices are stable under non-negative powers. We now extend this to all integer powers. The key observation is that a 1-nullcyclic matrix is unipotent with nilpotent off-diagonal part.

be a closed walk of positive length $m$. If this closed walk is stationary, then all its arcs are loops, and its $N$-weight is 0, since every diagonal entry of $N$ is 0.

If the closed walk is not stationary, then it contains a nontrivial cycle by Lemma 2.2. The $N$-weight of this cycle is 0 (since any nontrivial cycle on $[n]$ has $N$-weight 0). Hence the $N$-weight of the whole closed walk is 0 as well, since the $N$-weight of the cycle is a factor of it⁶. This proves part (a).

(b) Let $i,j \in[n]$. The walk expansion (3) (applied to $N$ and $n$ instead of $A$ and $m$) expresses the entry $(N^n)_{i,j}$ as the sum of the $N$-weights of all length-$n$ walks $i=i_0 \to i_1 \to\cdots\to i_n=j$ of $K_n^{\to}$ from $i$ to $j$. Every such walk has a repeated vertex (by the pigeonhole principle, since $K_n^{\to}$ has only $n$ vertices), and therefore contains a closed subwalk of positive length. By part (a), this closed subwalk has $N$-weight 0. Thus the whole walk has $N$-weight 0 as well. Since $(N^n)_{i,j}$ has been expressed as the sum of the weights of such walks, we thus conclude that $(N^n)_{i,j}=0$. Hence all entries of $N^n$ are 0, proving $N^n=0$. This proves part (b).

(c) By part (b), we have $N^n=0$. Hence $A=I_n+N$ is invertible, with inverse

(by the geometric series formula, here truncated to a finite sum since $-N$ is nilpotent). (We could replace the upper limit of this sum by $n-1$, but we have no need for this.) We first show that $A^{-1}$ is 1-diagonal. Let $i\in[n]$. From (6), we obtain

For each $r\ge1$, the walk expansion (3) (applied to $N$ and $r$ instead of $A$ and $m$) expresses $(N^r)_{i,i}$ as a sum of $N$-weights of positive-length closed walks. These weights are all 0 by part (a). Hence, (7) simplifies to $(A^{-1})_{i,i}=1$. This shows that $A^{-1}$ is 1-diagonal.

It remains to show that $A^{-1}$ is nullcyclic. Let $C=(i_1,i_2,\ldots,i_k)$ be a nontrivial cycle on $[n]$, and set $i_{k+1}:=i_1$. We must show that $w_{A^{-1}}(C)=0$.

For each $j\in[k]$, we can compare $(i_j,i_{j+1})$-entries in (6) to obtain

(by (3), applied to $N$ and $r$ instead of $A$ and $m$). We can rewrite this further as

where the “signed $N$-weight” of a length-$r$ walk is defined to be $(-1)^r$ times the $N$-weight of this walk. Substituting this into

and then expanding the product, we express $w_{A^{-1}}(C)$ as a sum over $k$-tuples $(W_1,W_2,\ldots,W_k)$ of walks from $i_j$ to $i_{j+1}$ for each $j\in[k]$; the addends of the sum are the products of the signed $N$-weights of these walks $W_1,W_2,\ldots,W_k$. As in the proof of Proposition 2.3, we can replace these $k$-tuples $(W_1,W_2,\ldots,W_k)$ by their concatenations $W_1W_2\cdots W_k$, and then the addends are the signed $N$-weights of these concatenations. But each concatenation $W_1W_2\cdots W_k$ is a closed walk of positive length (since it contains the two distinct vertices $i_1$ and $i_2$), so its $N$-weight is 0 by part (a). Therefore all addends in the expansion of $w_{A^{-1}}(C)$ vanish, and thus $w_{A^{-1}}(C)=0$. This proves that $A^{-1}$ is nullcyclic. Since $A^{-1}$ is also 1-diagonal, we conclude that $A^{-1}$ is 1-nullcyclic. This completes the proof of part (c). □

Integral closure and cycle weights

We now turn towards the harder, “upstream” direction, from (1-)principled to (1-)nullcyclic. As we already mentioned, in general, a 1-principled matrix is not always nullcyclic; a counterexample is constructed in the footnote in [2 §6].⁷ However, (1-

over $R$, then $A$ is 1-principled, but $A^2$ is not, since $\det(A^2)_{\{2,3\}}=1-x^3\ne1$ in $R$. This counterexample is minimal in the sense that there are no matrices of size $\le3$ that are 1-principled but have non-1-principled powers. )principledness implies a weaker version of (1-)nullcyclicity, which we will later leverage to obtain the full property under certain conditions.

We will need the classical notion of integrality over an ideal, which we will now briefly recall; see [11] for a much more extensive treatment.

Thus, an element is integral over the zero ideal if and only if it is nilpotent. We shall use the following standard properties of integral closure of ideals.

Proof. Parts (a) and (c) are [11 Corollary 1.3.1]. Part (b) is trivial. Part (d) follows from (b) and (c): the inclusions $I \subseteq J \subseteq\overline{I}$ yield

We next need a combinatorial ingredient. A Hamilton cycle on a finite set $S$ means a cycle on $S$ whose vertices are all the elements of $S$. In other words, it means a Hamilton cycle of $K_S^{\to}$, where $K_S^{\to}$ is the digraph whose vertices are the elements of $S$ and whose arcs are all the pairs $(s,t)$ for $s,t \in S$. We observe two obvious facts:

1. Each Hamilton cycle on a subset $S$ of $[n]$ is a cycle on $[n]$. Conversely, each cycle on $[n]$ is a Hamilton cycle on $S$, where $S$ is the set of vertices of this cycle.

2. A cycle on a finite set $S$ is Hamilton if and only if it has length $|S|$.

We identify each cycle with its set of arcs (since the latter set uniquely determines the former cycle). The multiset union $H \uplus H'$ of two cycles $H$ and $H'$ is defined to be a multidigraph (i.e., a directed multigraph) whose multiset of arcs is obtained by combining the sets of arcs of $H$ and of $H'$. (If an arc appears in both $H$ and $H'$, then it will appear twice in this multiset union.)

Proof of Lemma 4.3. Choose a vertex $v \in S$ whose outgoing arcs in $H$ and $H'$ are distinct.⁸ Write these arcs as

where $a \ne b$. Let $P'$ be the directed path in $H'$ from $a$ back to $v$, and let $P$ be the directed path in $H$ from $b$ back to $v$. Then the walks

are cycles. Both have length at most $|S|-1$. Indeed, if the cycle $C$ had length $\ge|S|$, then it would be Hamilton, and thus the path $P'$ would contain every vertex. Hence the complementary path in $H'$ from $v$ to $a$ would consist of a single arc. This arc would be the outgoing arc $(v,b)$ of $v$ in $H'$, forcing $a=b$. The same argument applies to $C'$.

The cycles $C$ and $C'$ are arc-disjoint in the multidigraph $H \uplus H'$. Indeed:

1. The only $H$-arc used by $C$ is $e$, while the $H$-arcs used by $C'$ lie in $P$, which does not use $e$ because $P$ ends at $v$. Thus, $C$ and $C'$ have no $H$-arcs in common.

2. Similarly, $C$ and $C'$ have no $H'$-arcs in common.

Remove the arcs of the two cycles $C$ and $C'$ from this multidigraph $H \uplus H'$. The remaining multidigraph is balanced⁹, because both the original multidigraph $H \uplus H'$ and the removed union $C \cup C'$ are balanced. Hence its arcs can be partitioned into cycles¹⁰. None of these new cycles contains $v$, since both outgoing arcs from $v$ in $H \uplus H'$ have been removed when we removed the arcs of $C$ and $C'$. Thus every new cycle has length at most $|S|-1$.

We have therefore partitioned the $2|S|$ arcs of $H \uplus H'$ into cycles of length at most $|S|-1$. Consequently, the number of these cycles is at least

that is, at least $3$ (since it is an integer). This proves the lemma.

Let $A=(a_{i,j})_{i,j\in[n]}$ be a matrix over a commutative ring $R$. For every integer $r\ge2$, let $K_{<r}(A)$ denote the ideal of $R$ generated by the $A$-weights of all nontrivial cycles on $[n]$ whose length is strictly smaller than $r$. Thus, $K_{<2}(A)=0$ (since a nontrivial cycle cannot have length smaller than $2$).

Proof. Pick any $i\ne j$ in $[t]$. By Lemma 4.3, the multiset union of the two distinct Hamilton cycles $H_i$ and $H_j$ on $S$ can be partitioned into at least three cycles of length strictly smaller than $r$. These latter cycles are all nontrivial, since they cannot contain any loops (indeed, all their arcs must be arcs of the original two Hamilton cycles, but those did not contain any loops). Hence, their $A$-weights belong to $K_{<r}(A)$. Since the product of the $A$-weights is unchanged by repartitioning the same multiset of arcs, this shows that

Thus, we have proved (8) for any $i \ne j$ in $[t]$.

Now, pair off $2\lfloor t/2\rfloor$ of the $t$ Hamilton cycles $H_1,H_2,\ldots,H_t$. Multiplying the inclusions (8) for these pairs, and multiplying by the $A$-weight of the remaining cycle if $t$ is odd, gives

Since $3\lfloor t/2\rfloor\ge t$ for every $t \ge2$, the right hand side is contained in $K_{<r}(A)^t$.

We can now state the universal algebraic result. For any matrix $A=(a_{i,j})_{i,j\in[n]}$ over any commutative ring $R$, we define the principal-minor-defect ideal of $A$ to be the ideal

(that is, the ideal of $R$ generated by all $2^n$ differences $\det A_S-\prod_{i\in S}a_{i,i}$, where $S$ ranges over the subsets of $[n]$). Note that the generators $\det A_S-\prod_{i\in S}a_{i,i}$ of this ideal for subsets $S$ satisfying $|S|\le1$ are zero, since the determinant of a $1\times1$-matrix or of a $0\times0$-matrix is the product of its diagonal entries.

Proof. We must show that each nontrivial cycle $H$ on $[n]$ satisfies $w_A(H)\in\overline{J(A)}$. In other words, we must show that for each $r\ge2$ and each $r$-element subset $S$ of $[n]$, each Hamilton cycle $H$ on $S$ satisfies $w_A(H)\in\overline{J(A)}$ (since any nontrivial cycle is a Hamilton cycle on a subset of size $\ge2$).

We use strong induction on $r$. Fix an $r$-element subset $S\subseteq[n]$, where $r\ge2$, and let $\mathcal{H}_S$ be the set of all Hamilton cycles on $S$. For every $H\in\mathcal{H}_S$, set

The sign $(-1)^{r-1}$ is the sign of the cyclic permutation corresponding to $H$ (that is, of the permutation of $S$ that sends each vertex of $H$ to the next vertex that follows it on $H$).

Set

We first show that each $z_H$ is integral over $L$. Let $e_t$ be the $t$-th elementary symmetric polynomial in the elements $z_H$ for $H \in\mathcal{H}_S$. In particular, $e_0 = 1$ and $e_1 = \sum_{H\in\mathcal{H}_S} z_H$. We shall now use the determinant expansion (1) to show that

Proof of (9). Each addend on the right-hand side of (1) corresponds to some permutation $\pi\in\mathcal{S}_S$. We can thus classify these addends into three classes:

Class 1 consists of the single addend for the permutation $\pi= \operatorname{id} \in\mathcal{S}_S$. This addend is

Class 2 consists of the addends corresponding to permutations $\pi$ that are $r$-cycles. Such permutations $\pi$ are in a one-to-one correspondence with the Hamilton cycles $H \in\mathcal{H}_S$ (indeed, each such permutation $\pi$ gives rise to the Hamilton cycle $(\pi^0(s),\pi^1(s),\ldots,\pi^{r-1}(s))$ for an arbitrary $s \in S$; the choice of $s$ is immaterial). The addend corresponding to a given Hamilton cycle $H \in\mathcal{H}_S$ is

Class 3 consists of the addends corresponding to permutations $\pi\ne\operatorname{id}$ that have at least two cycles. For such a permutation $\pi$, all cycles of $\pi$ must have length smaller than $r$ (since a cycle of length $\ge r$ would cover all elements of $S$, thus leaving no room for a second cycle), and at least one of these cycles must be nontrivial (because $\pi\ne\operatorname{id}$). Therefore, the corresponding addend contains the $A$-weight of a nontrivial cycle of length strictly smaller than $r$ as a factor; hence, this addend belongs to $K_{<r}(A) = K \subseteq L$, thus is $\equiv0 \pmod L$.

Hence, reduced modulo $L$, the equality (1) becomes

Therefore,

(since the definition of $J(A)$ yields $\det A_S - \prod_{i\in S} a_{i,i} \in J(A) \subseteq L$). That is, $\sum_{H\in\mathcal{H}_S} z_H \in L$. In other words, $e_1 \in L$ (since $e_1 = \sum_{H\in\mathcal{H}_S} z_H$). This proves (9). ∎

Now we shall generalize (9) by showing that

Proof of (4.3). If $t = 0$, then this is obvious (since $L^0 = R$). If $t = 1$, then it follows from (9). Thus, assume that $t \ge2$ henceforth. Now, $e_t$ is defined as the sum of the $t$-wise products of the $z_H$'s with $H \in\mathcal{H}_S$. Each addend in this sum is, up to sign, a product of the $A$-weights of $t$ distinct Hamilton cycles on $S$ (since the $z_H$'s are, up to sign, the $A$-weights of these cycles). But Lemma 4.5 shows that each such product belongs to $K_{<r}(A)^t$. Therefore, their sum $e_t$ belongs to $K_{<r}(A)^t$ as well, and thus also to $L^t$ (since $K_{<r}(A) = K \subseteq L$). This proves (10).

But Viète’s formulas show that every $z_H$ is a root of the monic polynomial

whose $X^{|\mathcal{H}_S|-t}$-coefficient belongs to $L^t$ (by (10)). Thus every $z_H$ is integral over $L$. Therefore, every $w_A(H)$ is integral over $L$ as well (since $z_H$ is $w_A(H)$ up to sign). In other words,

By the induction hypothesis, the $A$-weights of all nontrivial cycles of length strictly smaller than $r$ belong to $\overline{J(A)}$. Since $\overline{J(A)}$ is an ideal, this yields

(since $K = K_{<r}(A)$ is the ideal generated by these $A$-weights). Hence $L = J(A) + K \subseteq\overline{J(A)}$ (since $J(A) \subseteq\overline{J(A)}$ and $K \subseteq\overline{J(A)}$). Thus,

Hence, Lemma 4.2 (d) now gives $\overline{L} = \overline{J(A)}$. Thus, (11) rewrites as

In other words, each Hamilton cycle $H$ on $S$ satisfies $w_A(H) \in\overline{J(A)}$. This completes the induction.

Remark 4.7. The relation between principal minors and cycle weights has an algebro-geometric antecedent in the work of Lin and Sturmfels [6 Proposition 4, Lemma 6 and Proposition 7]. Over $\mathbb{C}$, they describe the change of coordinates between principal minors and cycle-sums, give a cycle decomposition closely related to Lemma 4.3, and prove that the algebra generated by the individual cycle monomials is integral over the algebra generated by the principal minors. In particular, [6 Lemma 6] is a stronger version of our Lemma 4.3, whereas [6 Proposition 7] is an analogue of our Theorem 4.6 for integrality over rings rather than over ideals.

Proof. Since $A$ is principled, each subset $S$ of $[n]$ satisfies $\det A_S = \prod_{i\in S} a_{i,i}$ and therefore $\det A_S - \prod_{i\in S} a_{i,i} = 0$. Thus, $J(A) = 0$ (since we have just shown that all generators of $J(A)$ are 0). Hence, Theorem 4.6 shows that every nontrivial cycle’s $A$-weight is integral over the zero ideal, and therefore nilpotent.

Proof. A reduced ring has no nonzero nilpotent elements, so the first claim follows from Corollary 4.8. The second then follows from Corollary 2.4.

Proof. Every 1-principled matrix is principled (by Proposition 1.5). Hence, the first claim of the corollary follows from the first claim of Corollary 4.9, combined with the fact that every 1-principled matrix is 1-diagonal (see Proposition 1.5). The second claim then follows from Corollary 3.6.

Quotients by integrally closed ideals

The general case

The universal theorems from the preceding section have the following immediate consequence.

Proof. Choose a matrix $\widetilde{A} = (\widetilde{a}_{i,j})_{i,j\in[n]}$ over $D$ whose image modulo $I$ is $A$. Since $A$ is principled, we have

Thus, $J(\widetilde{A}) \subseteq I$. By Theorem 4.6, every nontrivial cycle $C$ on $[n]$ satisfies $w_{\widetilde{A}}(C) \in J(\widetilde{A}) \subseteq\overline{I}$ (by Lemma 4.2 (b), since $J(\widetilde{A}) \subseteq I$) and therefore $w_{\widetilde{A}}(C) \in\overline{I} = I$ (since $I$ is integrally closed). Reducing modulo $I$, we obtain $w_A(C) = 0$ for every nontrivial cycle $C$. Hence $A$ is nullcyclic.

Proof. The matrix $A$ is 1-principled. By Proposition 1.5, this entails that $A$ is 1-diagonal and principled. Hence, Theorem 5.1 shows that $A$ is nullcyclic. Since $A$ is 1-diagonal, we thus conclude that $A$ is 1-nullcyclic.

Proof of Theorem 1.2. By Theorem 5.2, the matrix $A$ is 1-nullcyclic. Hence Corollary 3.6 shows that $A^m$ is 1-principled for every $m \in\mathbb{Z}$.

Proof of Theorem 1.9. By Theorem 5.1, the matrix $A$ is nullcyclic. Hence Corollary 2.4 shows that $A^m$ is principled for every $m \in\mathbb{N}$.

The rings $\mathbb{Z}/d$

The case of the ring $\mathbb{Z}/d = \mathbb{Z}/d\mathbb{Z}$ admits a particularly elementary application of Theorem 4.6. This relies on the following well-known fact, which we prove here for the sake of completeness:

Proof. Every ideal of $\mathbb{Z}$ has the form $d\mathbb{Z}$ for some $d \in\mathbb{N}$. The claim is clear for $d = 0$, since the only nilpotent integer is 0. Assume that $d > 0$, and let $x \in\mathbb{Z}$ be integral over $d\mathbb{Z}$. Thus, for some positive integer $r$, we have

Write $c_j=d^jb_j$ with $b_j\in\mathbb{Z}$, and put $y=x/d\in\mathbb{Q}$. Dividing the equation (12) by $d^r$ gives

Thus $y$ is a rational root of a monic polynomial in $\mathbb{Z}[X]$. To see directly that $y \in\mathbb{Z}$, write $y=a/b$ in lowest terms with $b > 0$. After multiplication by $b^r$, the equation (13) shows that $b \mid a^r$. Since $\gcd(a,b)=1$, this forces $b=1$. Hence $y\in\mathbb{Z}$, so $x=dy\in d\mathbb{Z}$.

Proof. The ideal $d\mathbb{Z}$ of $\mathbb{Z}$ is integrally closed by Lemma 5.3. Hence, Theorem 1.2 (applied to $D=\mathbb{Z}$ and $I=d\mathbb{Z}$) shows that $A^m$ is 1-principled for every $m\in\mathbb{Z}$.

Remark 5.5. Our above proof of Corollary 5.4 is self-contained. Indeed, the only result we have used without proof is Lemma 4.2, which in this case is being applied to $R=\mathbb{Z}$; but all claims of this lemma follow from Lemma 5.3 when $R=\mathbb{Z}$.

The reader can easily state and prove an analogue of Corollary 5.4 with “1-principled” replaced by “principled”.

Prüfer domains

We next give a broad class of domains for which every ideal is integrally closed.

For background on Prüfer domains and their equivalent characterizations, see [10 §XII.3] and [8].

The reader can easily state and prove an analogue of Corollary 5.8 with “1-principled” replaced by “principled”.

Normal domains

Recall that a normal domain is a domain that is integrally closed in its fraction field. Every principal ideal of a normal domain is integrally closed; see [11 Proposition 1.5.2]. Therefore Theorem 1.2 yields the following.