Proof. Let \(A=\left( a_{i,j} \right)_{i,j\in\left[ n \right]}\) be a strongly \(1\)-principled \(n\times n\)-matrix. Let \(S\subseteq\left[ n \right]\). We expand \[\det A_{S} = \sum_{\pi\in\mathfrak{S}_S}\operatorname{sgn}\left( \pi \right) \prod_{i\in S}a_{i,\pi(i)} \label{eq46lem46strong-implies-principled461}\tag{1}\] (where \(\mathfrak{S}_S\) is the group of all permutations of \(S\)). The identity permutation \(\operatorname{id}\in \mathfrak{S}_S\) contributes \[\operatorname{sgn}\left( \operatorname{id} \right) \prod_{i\in S}a_{i,\operatorname{id}(i)} = \prod_{i\in S}a_{i,i} = 1 \qquad \left( \text{since a_{i,i} = 1 for all i} \right)\] to the right-hand side of (1 ). Every non-identity permutation \(\pi \in \mathfrak{S}_S\) has at least one nontrivial cycle \(\left( i_1, i_2, \ldots, i_k\right)\) in its cycle decomposition. The corresponding addend on the right-hand side of (1 ) therefore contains, as a factor, the \(A\)-weight of this nontrivial cycle. This factor is \(0\), since \(A\) is strongly \(1\)-principled. Hence all non-identity addends on the right-hand side of (1 ) vanish, and we conclude that \(\det A_{S}=1\). That is, \(A\) is \(1\)-principled. ◻

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=\left( a_{i,j} \right)_{i,j\in\left[ n \right]}\). We also use \(B_{i,j}\) to refer to the \(\left( i,j\right)\)-th entry of any matrix \(B\); thus, \(A_{i,j}=a_{i,j}\) for all \(i,j\in\left[ n \right]\). Since \(A\) is strongly \(1\)-principled, all diagonal entries of \(A\) are \(1\): For each \(i\in\left[ n \right]\), we have \[a_{i,i} =1.\label{pf46lem46strong-powers46aii}\tag{2}\]

First, we show that every diagonal entry of \(A^{m}\) is \(1\). Fix \(i\in \left[ n \right]\). It is well-known (see, e.g., [4]; also, the weighted version of [3]) that for any two vertices \(i\) and \(j\) of \(K_{n}^{\rightarrow}\), we have ⁴ \[\left( A^{m}\right)_{i,j} = \sum_{\substack{i=i_{0}\rightarrow i_{1}\rightarrow\cdots \rightarrow i_{m}=j\\\text{is a walk of }K_{n}^{\rightarrow}}} a_{i_{0},i_{1}}a_{i_{1},i_{2}}\cdots a_{i_{m-1},i_{m}} .\label{pf46lem46strong-powers461}\tag{3}\] 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}\rightarrow i_{1}\rightarrow\cdots\rightarrow i_{m}=j\). Thus, (3 ) says that \[\left( A^{m}\right)_{i,j} = \left( \text{sum of the A-weights of all length-m walks from i to j} \right). \qquad\qquad \label{pf46lem46strong-powers462}\tag{4}\]

In particular, \(\left( A^{m}\right)_{i,i}\) is the sum of the \(A\)-weights of all length-\(m\) walks from \(i\) to \(i\). The stationary walk \(i=i\rightarrow i\rightarrow\cdots\rightarrow 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 (2 )). Each of the other length-\(m\) walks from \(i\) to \(i\) contains a nontrivial cycle by Lemma 1 (since it is a closed walk but not stationary). Since the latter cycle has \(A\)-weight \(0\) (because \(A\) is strongly \(1\)-principled), 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, \(\left( A^{m}\right)_{i,i}\) is the sum of a single \(1\) (corresponding to the stationary walk \(i=i\rightarrow i\rightarrow\cdots\rightarrow i=i\)) and a lot of \(0\)’s (coming from all the other walks). Therefore, \[\left( A^{m}\right)_{i,i}=1. \label{pf46lem46strong-powers463}\tag{5}\]

Forget that we fixed \(i\). So we have proved 5 for each \(i \in \left[ n \right]\).

It remains to prove that every nontrivial cycle on \(\left[ n \right]\) has \(A^{m}\)-weight \(0\). Let\[C=\left( i_{1},i_{2},\ldots,i_{k}\right)\] be a nontrivial cycle on \(\left[ n \right]\), with length \(k>1\). We must show that \(w_{A^m} \left( C \right) = 0\).

Note that \(i_1 \neq 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, \[\begin{align} w_{A^m} \left( C \right) &= \left( A^{m}\right)_{i_{1},i_{2}}\left( A^{m}\right)_{i_{2},i_{3}}\cdots\left( A^{m}\right)_{i_{k},i_{1}} = \prod_{j=1}^{k}\left( A^{m}\right)_{i_{j},i_{j+1}} \\ &= \prod_{j=1}^{k} \left( \text{sum of the A-weights of all length-m walks from i_j to i_{j+1}} \right) \end{align}\] (by 4 ). Expanding this product, we obtain a sum over all \(k\)-tuples of length-\(m\) walks from \(i_{j}\) to \(i_{j+1}\) for each \(j\in\left[ k \right]\). The addend corresponding to such a \(k\)-tuple is the product of the \(A\)-weights of all these walks; but this is, of course, the \(A\)-weight of the closed walk (of length \(km\)) obtained by concatenating these \(k\) walks. This closed walk is not stationary (since \(i_1 \neq i_2\) are two distinct vertices on it). Hence it contains a nontrivial cycle, again by Lemma 1. The \(A\)-weight of this cycle is \(0\) since \(A\) is strongly \(1\)-principled; but it is a factor of the \(A\)-weight of the walk. Thus, the whole closed walk has \(A\)-weight \(0\) as well.

Thus, we have shown that \(w_{A^m} \left( C \right)\) is a sum of \(A\)-weights of certain closed walks, but each of these closed walks has \(A\)-weight \(0\). Hence, \[w_{A^m} \left( C \right) = 0.\] Combined with 5 , this completes the proof of the fact that \(A^{m}\) is strongly \(1\)-principled. The proposition is proved. ◻

Proof. The matrix \(A^m\) is strongly \(1\)-principled by Proposition 3, and therefore is \(1\)-principled by Proposition 2. ◻

Proof. Parts (a) and (c) are [5]. Part (b) is trivial. Part (d) follows from (b) and (c): the inclusions \(I\subseteq J\subseteq\overline{I}\) yield \[\overline{I}\subseteq\overline{J}\subseteq \overline{\overline{I}}=\overline{I}. \qedhere\] ◻

Proof of Lemma 3.. Choose a vertex \(v\in S\) whose outgoing arcs in \(H\) and \(H'\) are distinct.⁵ Write these arcs as \[e=(v,a)\in H\qquad\text{and}\qquad e'=(v,b)\in H',\] where \(a\neq 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 \[\begin{align} C &:= P'e \qquad \text{(that is, the path P' followed by the arc e)} \qquad \text{ and } \\ C' &:= Pe' \qquad \text{(that is, the path P followed by the arc e')} \end{align}\] are cycles. Both have length at most \(\left|S\right| - 1\). Indeed, if the cycle \(C\) had length \(\geq \left|S\right|\), 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 \(\left|S\right| - 1\).

We have therefore partitioned the \(2\left|S\right|\) arcs of \(H\uplus H'\) into cycles of length at most \(\left|S\right|-1\). Consequently, the number of these cycles is at least \[\frac{2\left|S\right|}{\left|S\right|-1} > 2,\] that is, at least \(3\) (since it is an integer). This proves the lemma. ◻

Proof. Pick any \(i \neq j\) in \(\left[ t \right]\). By Lemma 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 \[\begin{align} w_A(H_i)w_A(H_j)\in K_{<r}(A)^3. \label{pf46lem46products-Hamilton-cycles464} \end{align}\tag{6}\] Thus, we have proved 6 for any \(i \neq j\) in \(\left[ t \right]\).

Now, pair off \(2\left\lfloor t/2\right\rfloor\) of the \(t\) Hamilton cycles \(H_1,H_2,\ldots,H_t\). Multiplying the inclusions 6 for these pairs, and multiplying by the \(A\)-weight of the remaining cycle if \(t\) is odd, gives \[w_A(H_1)w_A(H_2)\cdots w_A(H_t) \in K_{<r}(A)^{3\left\lfloor t/2\right\rfloor}.\] Since \(3\left\lfloor t/2\right\rfloor\geq t\) for every \(t\geq2\), the right hand side is contained in \(K_{<r}(A)^t\). ◻

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

We use strong induction on \(r\). Fix an \(r\)-element subset \(S\subseteq\left[ n \right]\), where \(r\geq2\), and let \(\mathcal{H}_S\) be the set of all Hamilton cycles on \(S\). For every \(H\in\mathcal{H}_S\), set \[z_H:=(-1)^{r-1}w_A(H).\] 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 \[K:=K_{<r}(A) \qquad\text{and}\qquad L:=J(A)+K.\] 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 \[e_1 \in L. \label{eq46Hamilton-e1-in-L}\tag{7}\]

Now we shall generalize 7 by showing that \[\begin{align} e_t \in L^t \qquad \text{ for each } t \geq 0. \label{eq46Hamilton-et-in-Lt} \end{align}\tag{8}\]

But Viète’s formulas show that every \(z_H\) is a root of the monic polynomial \[\prod_{G\in\mathcal{H}_S}(X-z_G) =X^{\left|\mathcal{H}_S\right|}-e_1X^{\left|\mathcal{H}_S\right|-1} +e_2X^{\left|\mathcal{H}_S\right|-2}-\cdots \in R\left[X\right],\] whose \(X^{\left|\mathcal{H}_S\right|-t}\)-coefficient belongs to \(L^t\) (by 8 ). 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, \[\begin{align} w_A(H) \in \overline{L} \qquad \text{ for each } H \in \mathcal{H}_S. \label{eq46wAH-in-L1} \end{align}\tag{9}\]

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 \[K\subseteq\overline{J(A)}\] (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, \[J(A) \subseteq L \subseteq \overline{J(A)}.\] Hence, Lemma 2 (d) now gives \(\overline{L} = \overline{J(A)}\). Thus, 9 rewrites as \[\begin{align} w_A(H) \in \overline{J(A)} \qquad \text{ for each } H \in \mathcal{H}_S. \end{align}\] In other words, each Hamilton cycle \(H\) on \(S\) satisfies \(w_A(H) \in \overline{J(A)}\). This completes the induction. ◻

Proof. In this case \(J(A)=0\) (since \(A\) is \(1\)-principled, so that all generators of \(J(A)\) are \(0\)). Thus, Theorem 5 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 2. The second then follows from Corollary 1. ◻

Proof. Choose a matrix \(\widetilde{A}\) over \(D\) whose image modulo \(I\) is \(A\). Since \(A\) is \(1\)-principled, we have \[\det \widetilde{A}_S-1\in I \qquad\text{for every }S\subseteq\left[ n \right].\] Thus \(J(\widetilde{A})\subseteq I\). By Theorem 5, every nontrivial cycle \(C\) on \(\left[ n \right]\) satisfies \(w_{\widetilde{A}}(C) \in \overline{J(\widetilde{A})} \subseteq \overline{I}\) (by Lemma 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\left( C \right) = 0\) for every nontrivial cycle \(C\). Also, the diagonal entries of \(A\) are \(1\), since they are its \(1\times1\) principal minors. Hence \(A\) is strongly \(1\)-principled. ◻

Proof of Theorem 1. By Theorem 6, the matrix \(A\) is strongly \(1\)-principled. Hence Corollary 1 shows that \(A^m\) is \(1\)-principled for every \(m\in\mathbb{N}\). ◻

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 \[\begin{align} x^r+c_1x^{r-1}+\cdots+c_rx^0=0 \qquad \text{with }c_j\in \left( d\mathbb{Z} \right)^j = d^j\mathbb{Z}. \label{pf46lem46Z-ideals-integrally-closed461} \end{align}\tag{10}\] Write \(c_j=d^jb_j\) with \(b_j\in\mathbb{Z}\), and put \(y=x/d\in\mathbb{Q}\). Dividing the equation 10 by \(d^r\) gives \[\begin{align} y^r+b_1y^{r-1}+\cdots+b_ry^0=0. \label{pf46lem46Z-ideals-integrally-closed462} \end{align}\tag{11}\] 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 11 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. Hence, Theorem 1 (applied to \(D = \mathbb{Z}\) and \(I = d\mathbb{Z}\)) shows that \(A^m\) is \(1\)-principled for every \(m\in\mathbb{N}\). ◻

Proof. This is part of [6], but we give a proof for the sake of completeness.

Let \(I\) be an ideal of a Prüfer domain \(D\), and let \(x\in D\) be integral over \(I\). We must show that \(x \in I\).

Choose an equation \[\begin{align} x^r+c_1x^{r-1}+\cdots+c_rx^0=0 \qquad \text{with } c_j\in I^j \label{pf46Pruefer46eq1} \end{align}\tag{12}\] (since \(x\) is integral over \(I\)). Only finitely many elements of \(I\) are needed to express all the \(c_j\) as sums of products of \(j\) elements of \(I\). Let \(J\subseteq I\) be the finitely generated ideal generated by these elements. Then \(c_j\in J^j\) for every \(j\), so \(x\) is integral over \(J\).

Set \(L:=J+xD\). If \(J=0\), then 12 gives \(x^r=0\), whence \(x=0\) since \(D\) is a domain; thus the claim is clear. Hence we may assume that \(J\neq0\). Then both \(J\) and \(L\) are nonzero finitely generated ideals, and therefore invertible. Moreover, 12 yields \[x^r\in JL^{r-1}.\] Any other product of \(r\) generators of \(L=J+xD\) already contains a factor from \(J\) and thus belongs to \(JL^{r-1}\) as well. Hence, \(L^r \subseteq JL^{r-1}\). Since the opposite inclusion is obvious, we thus have shown that \[L^r=JL^{r-1}.\] Since \(L^{r-1}\) is invertible, we may cancel it and obtain \(L=J\). In particular, \(x\in L=J\subseteq I\). Thus \(I\) is integrally closed. ◻

Proof. Combine Lemma 6 with Theorem 1. ◻