Invariants

In the following is a short list of the invariants for shift equivalence over Z used in the database. It is just a short survey of the invariants, and for a more thorough reading you should consult other literature.

In the following A is a nonnegative integral square matrix of size r.

Entropy

For a shift X the entropy h(X) is defined as h(X) := lim_{n → ∞} |B_n(X)| ⁄ n, where B_n(X) is the number of different words of length n in X.

For the shift X_A we have |B_n(X_A)| = ∑_{1 ≤ i, j ≤ r} Aⁿ_{i j}, and we define h(A) := h(X_A) = lim_{n → ∞} (∑_{1 ≤ i, j ≤ r} Aⁿ_{i j}) ⁄ n.

Perron Eigenvalue

The Perron eigenvalue of the matrix A is the largest positive eigenvalue λ_A, i.e. there exists an eigenvector v_A such that λ_A v_A = A v_A, and if μ is another eigenvalue for A, then |μ| ≤ λ_A.

The interesting part about the Perron eigenvalue is the close relation to the entropy, since h(X_A) = log₂ λ_A.

Bowen-Franks Group

Let p be a polynomial with integral coefficients, such that p(0) = ± 1.The generalized Bowen-Franks group of A with respect to p is BF_p(A) := Z^r ⁄ Z^r p(A).

The reason that this is called the generalized Bowen-Franks group is that the Bowen-Franks group corresponds to the choice p(t) = 1 − t.

BF_p(A) is a finitely generated Abelian group, hence there exists a unique choice of nonnegative integers d₁, d₂, …, d_i ≠ 1 where each d_j divides d_{j + 1}, such that BF_p(A) is isomorphic to Z_d1 ⊕ Z_d2 ⊕ … ⊕ Z_di, where Z_d := Z ⁄ dZ for a positive integer d and Z₀ = Z.

Jordan Form

For a complex number λ and a positive integer m the m×m Jordan block for λ is defined as the m×m matrix J_m(λ) which has λ on the main diagonal, 1 directly above the main diagonal, and 0 elsewhere.

Every square matrix is similar over the complex numbers to a direct sum of Jordan blocks. This representation is unique up to the ordering of blocks, and it is known as the Jordan canonical form of the matrix, i.e. there exists complex numbers λ₁, λ₂, …, λ_k and positive integers m₁, m₂, …, m_k, such that A is similar to J(A) := J_m1(λ₁) ⊕ J_m2(λ₂) ⊕ … ⊕ J_mk(λ_k). The matrix J(A) is called the Jordan form of A.

As similarity is an equivalence relation it is easy to see that two matrices have the same Jordan form (up to the ordering of blocks) if and only if they are similar, and since the eigenvalues does not change under similarity the numbers λ_i must be eigenvalues of A with multiplicity m_i, but they are not necessarily distinct.

Now we can define the Jordan form away from zero of A, denoted by J^×(A), as the part of the Jordan form of A where the eigenvalues are nonzero, i.e. if J(A) = J_m1(λ₁) ⊕ J_m2(λ₂) ⊕ … ⊕ J_mk(λ_k), then J^×(A) := ⊕_{1 ≤ i ≤ k, λi ≠ 0} J_mi(λ_i).

It is the Jordan form away from zero which is an invariant for shift equivalence over Z.

As the set of numbers λ_i in J^×(A) are all of the non zero eigenvalues of A we can see that the Perron eigenvalue λ_A is in this set, hence the Jordan form away from zero is a better invariant than the Perron eigenvalue.

Ideal Class

For an integral domain D we define an ideal a as a subset of D which is closed under linear combinations with coefficients from D.

A subset a in the field of fractions of D, is called a fractional ideal over D, if there exists a nonzero d ∈ D such that da is an ideal of D.

We will call two nonzero fractional ideals a and b from D equivalent, if there exists two nonzero elements a′, b′ ∈ D such that a′a = b′b.

An ideal class in D is a class of equivalent fractional ideals from D.

Let λ_A be the Perron eigenvalue of the nonnegative integral square matrix A, and let v_A be a right Perron eigenvector for A with entries in Z[λ]. For each integral domain D⊇Z[λ], we define the ideal class of A in D, ℑ_D(A) as the ideal class of the ideal spanned by the entries of v_A.

The ideal class in the domain Z[1/λ] is an invariant for shift equivalence over Z, where λ is the common Perron eigenvalue of the equivalent matrices.

There is a problem with the domain Z[1/λ] as it is not in general finitely generated over Z. If it is finitely generated, then one can show Z[1/λ] ⊆ O, where O is the maximal order of the number field Q(λ), that is the elements which are roots in monic integral polynomials. The maximal order is also known as the integers of Q(λ).

When Z[1/λ] ⊆ O, then ℑ_Z[1/λ](A) = ℑ_Z[1/λ](B) implies ℑ_O(A) = ℑ_O(B), hence in this case the ideal classes in the maximal order is an invariant.

The nice thing about the maximal order is, that it is easy to find the ideal classes here, and the ideal classes form a finite Abelian group under multiplication. It is the values of ℑ_O(A) which are computed and stored in the database. This is why the database sometimes says, that the ideal class is not an invariant.