The proof follows from the Definition 1.

For adjugate matrix we have identity \((x I - A) \operatorname {adj} (x I - A) = \det (x I - A) I\). Therefore,

The final equality follows from the Lemma 2.

The determinant is a sum over permutations \(\sigma \) of products \(\prod _{i=0}^{n-1} m_{\sigma (i),i}\). Each product has degree at most \(\sum _{i=0}^{n-1} \deg (m_{\sigma (i),i})\). Since a single element of a sum is at most the whole sum (when all terms are non-negative), this is bounded by \(\sum _{i=0}^{n-1} \sum _{j=0}^{n-1} \deg (m_{ij})\). The degree of a sum is at most the maximum degree of its summands.

This follows from the standard properties of the characteristic polynomial.

The adjugate entry \(\operatorname {adj}(\chi _A(x))_{ij}\) equals the determinant of the characteristic matrix with row \(j\) and column \(i\) removed from \(\chi _A(x)\).

This submatrix has diagonal entries from \(\chi _A(x)\) except at diagonal positions \(i\) and \(j\) (which are deleted). Since \(\chi _A(x)\) has diagonal entries of degree \(1\) (from \(x I\)) and off-diagonal entries of degree \(0\) (from \(-A\)), the submatrix has exactly \(n-2\) diagonal entries of degree \(1\) and all other entries of degree \(0\).

By Lemma 4, the determinant has degree at most \(n-2\).

The diagonal entries of \(\operatorname {adj}(x I - A)\) are characteristic polynomials of \((n-1) \times (n-1)\) submatrices, hence monic of degree \(n-1\) by Lemma 5.

The off-diagonal case follows directly from Lemma 6.

Lemma is trivially true for \(d=0\) so we can assume \(d \geq 1\). Write \(p(n) = an^d + r(n)\) where \(a \ge 1\) is the leading coefficient of \(p\), \(d = \deg (p)\), and \(\deg (r) {\lt} d\). For \(n \ge |p|\):

Since \(n \geq 1\), we have \(|r(n)| \leq B n^{d-1}\) where \(B = |p| - a\). Therefore,

The proof follows from Lemma 7 and Lemma 9. Let \(y = Mv\). Then \(y_i = \sum _{k=0}^{n-1} m_{ik} (k+1)\).

For each entry \(y_i\), we express it as evaluation of a polynomial \(p_i(x) = \sum _{k=0}^{n-1} m_{ik}(x) (k+1) \in \mathbb {Z}[x]\). By Lemma 7, the diagonal entry \(m_{ii}\) is monic of degree \(n-1\), while off-diagonal entries \(m_{ik}\) (for \(k \neq i\)) have degree at most \(n-2\). Therefore, the coefficient of \(x^{n-1}\) in \(p_i\) is \(i+1 {\gt} 0\) (dominated by the \(m_{ii} (i+1)\) term).

For the difference \(p_j - p_i\) with \(j {\gt} i\), the leading term comes from \((m_{jj} (j+1) - m_{ii} (i+1))\). Since both \(m_{jj}\) and \(m_{ii}\) are monic of degree \(n-1\), the leading coefficient of \(p_j - p_i\) is \((j+1) - (i+1) = j - i {\gt} 0\).

Similarly, for \(p_m(x) = \det (x I - A) - p_i(x)\), since \(\det (x I - A)\) is monic of degree \(n\) (by Lemma 5) and \(p_i\) has degree at most \(n-1\), the leading coefficient is 1.

Since \(p_0(x)\) has leading coefficient \(0+1 = 1 {\gt} 0\), we have \(y_0 {\gt} 0\) for sufficiently large \(x\).

Applying Lemma 9 to these polynomials with positive leading coefficients gives the existence of \(x_0\) such that all required inequalities hold for \(x {\gt} x_0\).

Let \(A = A_f\) be the adjacency matrix of \(f\) and let \(v = (1,2,\ldots ,n)^T\). By Lemma 10, there exists \(x_0\) such that for all integers \(x {\gt} x_0\), the entries \(y_i\) of \(y = \operatorname {adj}(xI - A)v\) satisfy:

where \(m(x) = \det (xI - A)\) is the characteristic polynomial of \(A\).

Since \(n {\gt} 1\), the polynomial \(m(x)\) is monic of degree \(n \geq 2\). Therefore, \(m - \text{id}\) (where \(\text{id}(x) = x\)) is also monic of degree \(n\), with leading coefficient \(1 {\gt} 0\).

By Lemma 9, the polynomial \(m - \text{id}\) is positive for all \(x \geq |m - \text{id}|\).

Set \(a_f = \max (x_0, |m - \text{id}|)\). For any \(a {\gt} a_f\), we have:

• \(a {\gt} x_0\), so the strict inequalities \(0 \leq y_0 {\lt} y_1 {\lt} \cdots {\lt} y_{n-1} {\lt} m(a)\) hold

• \(a \geq |m - \text{id}|\), so \((m - \text{id})(a) = m(a) - a {\gt} 0\), which gives \(m(a) {\gt} a\)

Define:

• \(m = m(a) = \det (aI - A)\) as the modulus (note: \(m {\gt} a\) by construction)

• \(j: \mathbb {Z}/n\mathbb {Z} \to \mathbb {Z}/m\mathbb {Z}\) by \(j(i) = y_i \bmod m\), where \(y = \operatorname {adj}(aI - A)v\)

Since \(0 \leq y_i {\lt} m\) for all \(i\) and the \(y_i\) are strictly increasing, \(j\) is injective.

By Lemma 3, we have \(y_{f(i)} = a \cdot y_i - m \cdot v_i\) for all \(i\). Taking this equation modulo \(m\) gives:

Therefore, \(j\) is a linear representation of \(f\) with modulus \(m {\gt} a\) and multiplier \(a \in \mathbb {Z}/m\mathbb {Z}\).

For \(n {\gt} 1\), apply Lemma 12 to obtain a threshold \(a_f\) and choose \(a = a_f + 1 {\gt} a_f\). The lemma provides an explicit construction of a linear representation for \(f\) with multiplier \(a_f + 1\).

For \(n = 1\), the result is trivial: there is only one element in \(\mathbb {Z}/1\mathbb {Z}\) (namely 0), so any function satisfies \(f(0) = 0\). We can use \(m = 1\), the identity map \(j = \operatorname {id}\), and multiplier \(0\), giving \(j(f(0)) = 0 = 0 \cdot j(0)\) in \(\mathbb {Z}/1\mathbb {Z}\).