Wednesday, September 28, 2022
HomeMathUtilizing the Smith regular type to govern lattice subgroups and closed torus...

Utilizing the Smith regular type to govern lattice subgroups and closed torus subgroups

Let {M_{n times m}({bf Z})} denote the area of {n times m} matrices with integer entries, and let {GL_n({bf Z})} be the group of invertible {n times n} matrices with integer entries. The Smith regular type takes an arbitrary matrix {A in M_{n times m}({bf Z})} and factorises it as {A = UDV}, the place {U in GL_n({bf Z})}, {V in GL_m({bf Z})}, and {D} is an oblong diagonal matrix, by which we imply that the principal {min(n,m) times min(n,m)} minor is diagonal, with all different entries zero. Moreover the diagonal entries of {D} are {alpha_1,dots,alpha_k,0,dots,0} for some {0 leq k leq min(n,m)} (which can be the rank of {A}) with the numbers {alpha_1,dots,alpha_k} (referred to as the invariant components) principal divisors with  alpha_k. The invariant components are uniquely decided; however there could be some freedom to change the invertible matrices {U,V}. The Smith regular type could be computed simply; for example, in SAGE, it may be computed calling the {{tt smith_form()}} perform from the matrix class. The Smith regular type can be accessible for different principal splendid domains than the integers, however we’ll solely be centered on the integer case right here. For the needs of this submit, we’ll view the Smith regular type as a primitive operation on matrices that may be invoked as a “black field”.

On this submit I want to file learn how to use the Smith regular type to computationally manipulate two carefully associated courses of objects:

  • Subgroups {Gamma leq {bf Z}^d} of a regular lattice {{bf Z}^d} (or lattice subgroups for brief);
  • Closed subgroups {H leq ({bf R}/{bf Z})^d} of a regular torus {({bf R}/{bf Z})^d} (or closed torus subgroups for brief).

(This arose for me because of the want to really carry out (with a collaborator) some numerical calculations with various lattice subgroups and closed torus subgroups.) It’s potential that each one of those operations are already encoded in some present object courses in a computational algebra package deal; I’d have an interest to know of such packages and courses for lattice subgroups or closed torus subgroups within the feedback.

The above two courses of objects are isomorphic to one another by Pontryagin duality: if {Gamma leq {bf Z}^d} is a lattice subgroup, then the orthogonal complement

displaystyle  Gamma^perp := { x in ({bf R}/{bf Z})^d: langle x, xi rangle = 0 forall xi in Gamma }

is a closed torus subgroup (with {langle,rangle: ({bf R}/{bf Z})^d times {bf Z}^d rightarrow {bf R}/{bf Z}} the same old Fourier pairing); conversely, if {H leq ({bf R}/{bf Z})^d} is a closed torus subgroup, then

displaystyle  H^perp := { xi in {bf Z}^d: langle x, xi rangle = 0 forall x in H }

is a lattice subgroup. These two operations invert one another: {(Gamma^perp)^perp = Gamma} and {(H^perp)^perp = H}.

Instance 1 The orthogonal complement of the lattice subgroup

displaystyle  2{bf Z} times {0} = { (2n,0): n in {bf Z}} leq {bf Z}^2

is the closed torus subgroup

displaystyle  (frac{1}{2}{bf Z}/{bf Z}) times ({bf R}/{bf Z}) = { (x,y) in ({bf R}/{bf Z})^2: 2x=0} leq ({bf R}/{bf Z})^2

and conversely.

Allow us to focus first on lattice subgroups {Gamma leq {bf Z}^d}. As all such subgroups are finitely generated abelian teams, one method to describe a lattice subgroup is to specify a set {v_1,dots,v_n in Gamma} of turbines of {Gamma}. Equivalently, now we have

displaystyle  Gamma = A {bf Z}^n

the place {A in M_{d times n}({bf Z})} is the matrix whose columns are {v_1,dots,v_n}. Making use of the Smith regular type {A = UDV}, we conclude that

displaystyle  Gamma = UDV{bf Z}^n = UD{bf Z}^n

so specifically {Gamma} is isomorphic (with respect to the automorphism group {GL_d({bf Z})} of {{bf Z}^d}) to {D{bf Z}^n}. Specifically, we see that {Gamma} is a free abelian group of rank {k}, the place {k} is the rank of {D} (or {A}). This illustration additionally permits one to trim the illustration {A {bf Z}^n} right down to {U D'{bf Z}^k}, the place {D' in M_{d times k}} is the matrix fashioned from the {k} left columns of {D}; the columns of {UD'} then give a foundation for {Gamma}. Allow us to name this a trimmed illustration of {A{bf Z}^n}.

Instance 2 Let {Gamma leq {bf Z}^3} be the lattice subgroup generated by {(1,3,1)}, {(2,-2,2)}, {(3,1,3)}, thus {Gamma = A {bf Z}^3} with {A = begin{pmatrix} 1 & 2 & 3  3 & -2 & 1  1 & 2 & 3 end{pmatrix}}. A Smith regular type for {A} is given by

displaystyle  A = begin{pmatrix} 3 & 1 & 1  1 & 0 & 0  3 & 1 & 0 end{pmatrix} begin{pmatrix} 1 & 0 & 0  0 & 8 & 0  0 & 0 & 0 end{pmatrix} begin{pmatrix} 3 & -2 & 1  -1 & 1 & 0  1 & 0 & 0 end{pmatrix}

so {A{bf Z}^3} is a rank two lattice with a foundation of {(3,1,3) times 1 = (3,1,3)} and {(1,0,1) times 8 = (8,0,8)} (and the invariant components are {1} and {8}). The trimmed illustration is

displaystyle  A {bf Z}^3 = begin{pmatrix} 3 & 1 & 1  1 & 0 & 0  3 & 1 & 0 end{pmatrix} begin{pmatrix} 1 & 0  0 & 8  0 & 0 end{pmatrix} {bf Z}^2 = begin{pmatrix} 3 & 8  1 & 0  3 & 8 end{pmatrix} {bf Z}^2.

There are different Smith regular varieties for {A}, giving barely totally different representations right here, however the rank and invariant components will at all times be the identical.

By the above dialogue we are able to symbolize a lattice subgroup {Gamma leq {bf Z}^d} by a matrix {A in M_{d times n}({bf Z})} for some {n}; this illustration just isn’t distinctive, however we’ll tackle this problem shortly. For now, we deal with the query of learn how to use such information representations of subgroups to carry out primary operations on lattice subgroups. There are some operations which can be very simple to carry out utilizing this information illustration:

One may use Smith regular type to detect when one lattice subgroup {B {bf Z}^m leq {bf Z}^d} is a subgroup of one other lattice subgroup {A {bf Z}^n leq {bf Z}^d}. Utilizing Smith regular type factorization {A = U D V}, with invariant components alpha_k, the relation {B {bf Z}^m leq A {bf Z}^n} is equal after some manipulation to

displaystyle  U^{-1} B {bf Z}^m leq D {bf Z}^n.

The group {U^{-1} B {bf Z}^m} is generated by the columns of {U^{-1} B}, so this provides a take a look at to find out whether or not {B {bf Z}^{m} leq A {bf Z}^{n}}: the {i^{th}} row of {U^{-1} B} should be divisible by {alpha_i} for {i=1,dots,k}, and all different rows should vanish.

Instance 3 To check whether or not the lattice subgroup {Gamma'} generated by {(1,1,1)} and {(0,2,0)} is contained within the lattice subgroup {Gamma = A{bf Z}^3} from Instance 2, we write {Gamma'} as {B {bf Z}^2} with {B = begin{pmatrix} 1 & 0  1 & 2  1 & 0end{pmatrix}}, and observe that

displaystyle  U^{-1} B = begin{pmatrix} 1 & 2  -2 & -6  0 & 0 end{pmatrix}.

The primary row is in fact divisible by {1}, and the final row vanishes as required, however the second row just isn’t divisible by {8}, so {Gamma'} just isn’t contained in {Gamma} (however {4Gamma'} is); additionally an analogous computation verifies that {Gamma} is conversely contained in {Gamma'}.

One can now take a look at whether or not {B{bf Z}^m = A{bf Z}^n} by testing whether or not {B{bf Z}^m leq A{bf Z}^n} and {A{bf Z}^n leq B{bf Z}^m} concurrently maintain (there could also be extra environment friendly methods to do that, however that is already computationally manageable in lots of functions). This in precept addresses the problem of non-uniqueness of illustration of a subgroup {Gamma} within the type {A{bf Z}^n}.

Subsequent, we take into account the query of representing the intersection {A{bf Z}^n cap B{bf Z}^m} of two subgroups {A{bf Z}^n, B{bf Z}^m leq {bf Z}^d} within the type {C{bf Z}^p} for some {p} and {C in M_{d times p}({bf Z})}. We are able to write

displaystyle  A{bf Z}^n cap B{bf Z}^m = { Ax: Ax = By hbox{ for some } x in {bf Z}^n, y in {bf Z}^m }

displaystyle  = (A 0) { z in {bf Z}^{n+m}: (A B) z = 0 }

the place {(A B) in M_{d times n+m}({bf Z})} is the matrix fashioned by concatenating {A} and {B}, and equally for {(A 0) in M_{d times n+m}({bf Z})} (right here we use the change of variable {z = begin{pmatrix} x  -y end{pmatrix}}). We apply the Smith regular type to {(A B)} to put in writing

displaystyle  (A B) = U D V

the place {U in GL_d({bf Z})}, {D in M_{d times n+m}({bf Z})}, {V in GL_{n+m}({bf Z})} with {D} of rank {k}. We are able to then write

displaystyle  { z in {bf Z}^{n+m}: (A B) z = 0 } = V^{-1} { w in {bf Z}^{n+m}: Dw = 0 }

displaystyle  = V^{-1} ({0}^k times {bf Z}^{n+m-k})

(making the change of variables {w = Vz}). Thus we are able to write {A{bf Z}^n cap B{bf Z}^m = C {bf Z}^{n+m-k}} the place {C in M_{d times n+m-k}({bf Z})} consists of the correct {n+m-k} columns of {(A 0) V^{-1} in M_{d times n+m}({bf Z})}.

Instance 4 With the lattice {A{bf Z}^3} from Instance 2, we will compute the intersection of {A{bf Z}^3} with the subgroup {{bf Z}^2 times {0}}, which one may write as {B{bf Z}^2} with {B = begin{pmatrix} 1 & 0  0 & 1  0 & 0 end{pmatrix}}. We acquire a Smith regular type

displaystyle  (A B) = begin{pmatrix} 0 & 1 & 0  1 & 0 & 0  0 & 0 & 1 end{pmatrix} begin{pmatrix} 1 & 0 & 0 & 0 & 0  0 & 1 & 0 & 0 & 0  0 & 0 & 1 & 0 & 0 end{pmatrix} begin{pmatrix} 3 & -2 & 1 & 0 & 1  1 & 2 & 3 & 1 & 0  1 & 2 & 3 & 0 & 0  1 & 0 & 0 & 0 & 0  0 & 1 & 1 & 0 & 0 end{pmatrix}

so {k=3}. We’ve

displaystyle  (A 0) V^{-1} = begin{pmatrix} 0 & 0 & 1 & 0 & 0  0 & 0 & 3 & 0 & -8  0 & 0 & 1 & 0 & 0 end{pmatrix}

and so we are able to write {A{bf Z}^3 cap B{bf Z}^2 = C{bf Z}^2} the place

displaystyle  C = begin{pmatrix} 0 & 0  0 & -8  0 & 0 end{pmatrix}.

One can trim this illustration if desired, for example by deleting the primary column of {C} (and changing {{bf Z}^2} with {{bf Z}}). Thus the intersection of {A{bf Z}^3} with {{bf Z}^2 times {0}} is the rank one subgroup generated by {(0,-8,0)}.

An analogous calculation permits one to symbolize the pullback {T^{-1} (A {bf Z}^n) leq {bf Z}^{d'}} of a subgroup {A{bf Z}^n leq {bf Z}^d} through a linear transformation {T in M_{d times d'}({bf Z})}, since

displaystyle T^{-1} (A {bf Z}^n) = { x in {bf Z}^{d'}: Tx = Ay hbox{ for some } y in {bf Z}^m }

displaystyle  = (I 0) { z in {bf Z}^{d'+m}: (T A) z = 0 }

the place {(I 0) in M_{d' times d'+m}({bf Z})} is the concatenation of the {d' times d'} identification matrix {I} and the {d' times m} zero matrix. Making use of the Smith regular type to put in writing {(T A) = UDV} with {D} of rank {k}, the identical argument as earlier than permits us to put in writing {T^{-1}(A{bf Z}^n) = C {bf Z}^{d'+m-k}} the place {C in M_{d' times d'+m-k}} consists of the correct {d'+m-k} columns of {(I 0) V^{-1} in M_{d' times d'+m}({bf Z})}.

Amongst different issues, this enables one to explain lattices given by techniques of linear equations and congruences within the {A{bf Z}^n} format. Certainly, the set of lattice vectors {x in {bf Z}^d} that clear up the system of congruences

displaystyle  alpha_i | x cdot v_i      (1)

for {i=1,dots,k}, some pure numbers {alpha_i}, and a few lattice vectors {v_i in {bf Z}^d}, along with an extra system of equations

displaystyle  x cdot w_j = 0      (2)

for {j=1,dots,l} and a few lattice vectors {w_j in {bf Z}^d}, could be written as {T^{-1}(A {bf Z}^k)} the place {T in M_{k+l times d}({bf Z})} is the matrix with rows {v_1,dots,v_k,w_1,dots,w_l}, and {A in M_{k+l times k}({bf Z})} is the diagonal matrix with diagonal entries {alpha_1,dots,alpha_k}. Conversely, any subgroup {A{bf Z}^n} could be described on this type by first utilizing the trimmed illustration {A{bf Z}^n = UD'{bf Z}^k}, at which level membership of a lattice vector {x in {bf Z}^d} in {A{bf Z}^n} is seen to be equal to the congruences

displaystyle  alpha_i | U^{-1} x cdot e_i

for {i=1,dots,k} (the place {k} is the rank, {alpha_1,dots,alpha_k} are the invariant components, and {e_1,dots,e_d} is the usual foundation of {{bf Z}^d}) along with the equations

displaystyle  U^{-1} x cdot e_j = 0

for {j=k+1,dots,d}. Thus one can acquire a illustration within the type (1), (2) with {l=d-k}, and {v_1,dots,v_k,w_1,dots,w_{d-k}} to be the rows of {U^{-1}} so as.

Instance 5 With the lattice subgroup {A{bf Z}^3} from Instance 2, now we have {U^{-1} = begin{pmatrix} 0 & 1 & 0  0 & -3 & 1  1 & 0 & -1 end{pmatrix}}, and so {A{bf Z}^3} consists of these triples {(x_1,x_2,x_3)} which obey the (redundant) congruence

displaystyle  1 | x_2,

the congruence

displaystyle  8 | -3x_2 + x_3

and the identification

displaystyle  x_1 - x_3 = 0.

Conversely, one can use the above process to transform the above system of congruences and identities again right into a type {A' {bf Z}^{n'}} (although relying on which Smith regular type one chooses, the top outcome could also be a distinct illustration of the identical lattice group {A{bf Z}^3}).

Now we apply Pontryagin duality. We declare the identification

displaystyle  (A{bf Z}^n)^perp = { x in ({bf R}/{bf Z})^d: A^Tx = 0 }

for any {A in M_{d times n}({bf Z})} (the place {A^T in M_{n times d}({bf Z})} induces a homomorphism from {({bf R}/{bf Z})^d} to {({bf R}/{bf Z})^n} within the apparent vogue). This may be verified by direct computation when {A} is a (rectangular) diagonal matrix, and the overall case then simply follows from a Smith regular type computation (one can presumably additionally derive it from the category-theoretic properties of Pontryagin duality, though I can’t accomplish that right here). So closed torus subgroups which can be outlined by a system of linear equations (over {{bf R}/{bf Z}}, with integer coefficients) are represented within the type {(A{bf Z}^n)^perp} of an orthogonal complement of a lattice subgroup. Utilizing the trimmed type {A{bf Z}^n = U D' {bf Z}^k}, we see that

displaystyle  (A{bf Z}^n)^perp = { x in ({bf R}/{bf Z})^d: (UD')^T x = 0 }

displaystyle  = (U^{-1})^T { y in ({bf R}/{bf Z})^d: (D')^T x = 0 }

displaystyle  = (U^{-1})^T (frac{1}{alpha_1} {bf Z}/{bf Z} times dots times frac{1}{alpha_k} {bf Z}/{bf Z} times ({bf R}/{bf Z})^{d-k}),

giving an express illustration “in coordinates” of such a closed torus subgroup. Specifically we are able to learn off the isomorphism class of a closed torus subgroup because the product of a finite variety of cyclic teams and a torus:

displaystyle (A{bf Z}^n)^perp equiv ({bf Z}/alpha_1 {bf Z}) times dots times ({bf Z}/alpha_k{bf Z}) times ({bf R}/{bf Z})^{d-k}.

Instance 6 The orthogonal complement of the lattice subgroup {A{bf Z}^3} from Instance 2 is the closed torus subgroup

displaystyle  (A{bf Z}^3)^perp = { (x_1,x_2,x_3) in ({bf R}/{bf Z})^3: x_1 + 3x_2 + x_3

displaystyle  = 2x_1 - 2x_2 + 2x_3 = 3x_1 + x_2 + 3x_3 = 0 };

utilizing the trimmed illustration of {(A{bf Z}^3)^perp}, one can simplify this a bit of to

displaystyle  (A{bf Z}^3)^perp = { (x_1,x_2,x_3) in ({bf R}/{bf Z})^3: 3x_1 + x_2 + 3x_3

displaystyle  = 8 x_1 + 8x_3 = 0 }

and one may write this because the picture of the group {{ 0} times (frac{1}{8}{bf Z}/{bf Z}) times ({bf R}/{bf Z})} beneath the torus isomorphism

displaystyle  (y_1,y_2,y_3) mapsto (y_3, y_1 - 3y_2, y_2 - y_3).

In different phrases, one can write

displaystyle  (A{bf Z}^3)^perp = { (y,0,-y) + (0,-frac{3a}{8},frac{a}{8}): y in {bf R}/{bf Z}; a in {bf Z}/8{bf Z} }

in order that {(A{bf Z}^3)^perp} is isomorphic to {{bf R}/{bf Z} times {bf Z}/8{bf Z}}.

We are able to now dualize all the earlier computable operations on subgroups of {{bf Z}^d} to supply computable operations on closed subgroups of {({bf R}/{bf Z})^d}. As an example:

Instance 7 Suppose one needs to compute the sum of the closed torus subgroup {(A{bf Z}^3)^perp} from Instance 6 with the closed torus subgroup {{0}^2 times {bf R}/{bf Z}}. This latter group is the orthogonal complement of the lattice subgroup {{bf Z}^2 times {0}} thought-about in Instance 4. Thus now we have {(A{bf Z}^3)^perp + ({0}^2 times {bf R}/{bf Z}) = (C{bf Z}^2)^perp} the place {C} is the matrix from Instance 6; discarding the zero column, we thus have

displaystyle (A{bf Z}^3)^perp + ({0}^2 times {bf R}/{bf Z}) = { (x_1,x_2,x_3): -8x_2 = 0 }.



Please enter your comment!
Please enter your name here

Most Popular

Recent Comments