Results 1 to 7 of 7
Like Tree2Thanks
  • 1 Post By Deveno
  • 1 Post By Deveno

Math Help - Integer matrix

  1. #1
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    103
    Thanks
    14

    Integer matrix

    Hi
    For which positive integers n, does there exist a non-identity 2x2 matrix with integer entries, such that A^n=I?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,273
    Thanks
    666

    Re: Integer matrix

    consider the matrix

    A = \begin{bmatrix}\cos(2\pi/n)&-\sin(2\pi/n)\\ \sin(2\pi/n)&\cos(2\pi/n) \end{bmatrix}

    use induction to show that:

    A^k = \begin{bmatrix}\cos(2\pi k/n)&-\sin(2\pi k/n)\\ \sin(2\pi k/n)&\cos(2\pi k/n) \end{bmatrix}

    (hint: double-angle formulas)

    when are these integers (mis-read original question)?

    EDIT: this is a harder question that it appears.

    for such a matrix A, we obviously have det(A) = 1. for odd n, det(A) = 1, so A is in SL(2,Z). i shall have to think about this some more.
    Last edited by Deveno; December 16th 2012 at 12:39 PM.
    Thanks from HallsofIvy
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    103
    Thanks
    14

    Re: Integer matrix

    But there may be other forms for A that give more values for n,arn't there?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,273
    Thanks
    666

    Re: Integer matrix

    well, yes, for example, for n = 3, i found:

    A = \begin{bmatrix}0&1\\-1&-1 \end{bmatrix}

    so your question really is: what orders are possible for elements of GL(2,Z)?

    it is easy to exhibit cyclic subgroups of orders 2,3 and 4 (and thus elements of these orders). doing a little research i found this element of order 6:

    A = \begin{bmatrix}0&-1\\1&1 \end{bmatrix}

    going to think about the possible eigenvalues of such a matrix, now.

    EDIT: i found the answer, and it's...complicated. will post a full solution when i collect my thoughts.
    Last edited by Deveno; December 16th 2012 at 01:14 PM.
    Thanks from hedi
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,273
    Thanks
    666

    Re: Integer matrix

    ok, this is going to be sort of long.

    we're looking for elements of finite order in GL(2,Z) (this is the same as the orthogonal group, since any element of it must have determinant 1).

    well any such matrix A, lies in a finite subgroup G = <A>. so let's look for all finite subgroups of GL(2,Z).

    some elementary observations: if An = I, for odd n, A is in SL(2,Z), and if n is odd, A is either in SL(2,Z), or the coset R(SL(2,Z)), where R is the matrix:

    R = \begin{bmatrix}1&0\\0&-1 \end{bmatrix}

    this is because det:GL(2,Z) -->{-1,1} is multiplicative, and SL(2,Z) is the kernel of this map.

    so first, we're going to look at finite subgroups of SL(2,Z).

    claim #1: the map φ:GL(2,Z)-->GL(2,Z3) given by φ((aij)) = (aij mod 3) is a homomorphism, which induces a homomorphism φ':SL(2,Z)-->SL(2,Z3)

    the proof that φ is a homomorphism (of groups) is left to the reader. the fact that it induces the homomorphism φ' can be seen by det(φ(A)) = (det(A) mod 3), and -1 ≠ 1 (mod 3).

    claim #2 (this is where it gets interesting):

    if H is a finite subgroup of SL(2,Z), then φ' is an isomorphism of H with φ'(H).

    we're going to need several lemmas along the way.

    lemma #1: SL(2,Z) has a unique element of order 2: -I.

    suppose that A is in SL(2,Z) of order 2, and that λ is an eigenvalue for A. since A2 = I, we have that λ2 is an eigenvalue for I, that is λ2 = 1. so λ = 1.

    consider A as a matrix in SL(2,C) (where C is the complex field). i claim that A is diagonalizable over C. for suppose not. let u be an eigenvector for λ in C2(which must be a repeated eigenvalue, since we are assuming A is not diagonalizable).

    choose v such that B = {u,v} is a basis for C2. in this basis, the matrix for A is:

    A' = \begin{bmatrix}\lambda&a\\0&b \end{bmatrix}.

    clearly, we must have a = 0 (since A'(v) = A'([0,1]B) = [a,b]B = [0,λ]B), contradicting our assumption that A' is not diagonal. so A is diagonalizable.

    since 1 = det(A) is the product of its eigenvalues, it must have either both eigenvalues -1, or both eigenvalues 1. if both eigenvalues are 1, then:

    PAP-1 = I, so A = P-1IP = I, which is of order 1. so both eigenvalues are -1, hence:

    PAP-1 = -I, so A = P-1(-I)P = -I. this establishes the lemma.

    returning to claim #2: suppose that a non-identity matrix A in SL(2,Z) is in the kernel of φ'. clearly A does not have order 2, since only -I has order 2, and φ'(-I) is not the identity, it is:

    \begin{bmatrix}2&0\\0&2 \end{bmatrix} = \begin{bmatrix}-1&0\\0&-1 \end{bmatrix}

    (2 = -1 (mod 3)). since φ'(A) has trace 2 (mod 3), it follows that tr(A) is congruent to 2 mod 3.

    lemma 2: if A is a matrix of finite order n > 2 in SL(2,Z), then the eigenvalues of A (in C) are n-th complex roots of unity, and conjugate-pairs.

    the first part of this follows from the fact that if An = I, and λ is an eigenvalue in C for A, then λn = 1. from the characteristic polynomial for A, we see:

    det(xI - A) = (x - λ1)(x - λ2) = x2 - (λ12)x + λ1λ2

    this is a real polynomial (since the entries of A are integers, and thus real), hence:

    λ1 + λ2 is real. so Im(λ2) = -Im(λ1). also λ1λ2 is real, so:

    if λ1 = a + bi, then λ2 = a' - bi, then λ1λ2 = aa' - b2 + (a - a')bi.

    so (a - a')b = 0. if b = 0, then λ1 is a real n-th root of unity, so can only be 1 or -1. the polynomials we get in this case are:

    x2 - 1 <---implies A is of order 2, which we are not allowing
    (x - 1)2 <--implies A-I is nillpotent, but as we saw above, A is diagonalizable, so A-I is diagonalizable, and for a diagonal matrix D2 = 0 implies D = 0, which gives us A = I, of order 1.
    (x + 1)2 <---same problem, A+I is nilpotent, but A+I is diagonalizable, so we have A+I = 0, and thus A = -I, of order 2.

    so if the order of A > 2, b ≠ 0, so a = a', that is: λ2 = λ1* are conjugate-pairs. this proves the lemma.

    returning to claim #2:

    recall that the trace of a 2x2 matrix is the sum of its eigenvalues, so:

    |tr(A)| = |λ + λ*| < |λ| + |λ*| = 1 + 1 = 2 (we have a strict inequality since the imaginary part of λ is not 0).

    thus |tr(A)| = 0, or 1, so tr(A) = -1,0, or 1. of these, only -1 is congruent to 2 (mod 3), so we conclude that if A is in ker(φ'), tr(A) = -1.

    so (whew!) THIS means A is of the form:

    A = \begin{bmatrix}a&b\\c&-1-a \end{bmatrix}

    since A is in ker(φ') we have that b = 0 (mod 3), and c = 0 (mod 3), thus bc is divisible by 9. since A is in SL(2,Z) we have:

    a(-1-a) - bc = 1

    taking mod 9 of both sides, we have:

    a2 + a + 1 = 0 (mod 9). the proof that this has no solution (mod 9) is left to the reader (it's not hard). so there can BE no such a, which means that the only element of H in ker(φ') is the identity.

    thus φ'(H) is isomorphic to H.

    next, let's see if we can establish how big SL(2,Z3) is. first, let's look at GL(2,Z3). to pick an element of GL(2,Z3) it suffices to pick two vectors which are linearly independent in Z3xZ3.

    clearly, we can pick any non-zero vector for our first column, there are 8 of these. for our next vector, the only ones we can't pick are the 2 multiples of our first vector, which gives us 6 to choose from. so |GL(2,Z3)| = 48.

    now det:GL(2,Z3)-->{-1,1} is an ONTO homomorphism with kernel SL(2,Z3), so |SL(2,Z3)| = 48/2 = 24.

    so we have THIS consequence: ANY finite subgroup of SL(2,Z) is a subgroup with order dividing 24. in particular, any element of ODD order in GL(2,Z) must lie in SL(2,Z), and thus must have order an odd divisor of 24. the only odd divisors of 24 are 1 and 3.

    so for odd integers n, only 1 and 3 are possible. we have found examples for each of these.

    for even integers, it's a bit more rough going. i will continue this in another post, to keep it from being overly long.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    103
    Thanks
    14

    Re: Integer matrix

    Thank you so much.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,273
    Thanks
    666

    Re: Integer matrix

    continuing....

    ok, we need to know more about SL(2,Z3). in particular, we need to know what subgroups it might have. we already know it has a cyclic subgroup of order 3 (since we found a matrix in GL(2,Z) of order 3), but we can also show this directly:

    M = \begin{bmatrix}1&1\\0&1 \end{bmatrix}

    is a generator of a cyclic subgroup of SL(2,Z3) of order 3. it's also clear that -I is an element of order 2.

    what we need to know is:

    (*) does SL(2,Z3) have any subgroups of orders 4,6,8, or 12?

    to do so, we need to introduce a new idea: the normalizer in a group G of a subgroup K, N(K) = {x in G: xKx-1 = K}. clearly K is always a subgroup of N(K). the subgroup i have in mind is T = <M>, the matrix above.

    suppose that B is in N(T):

    BM^kB^{-1} = M^{k'}

    that is:

    \begin{bmatrix}x&y\\z&w \end{bmatrix} \begin{bmatrix}1&a\\0&1 \end{bmatrix} \begin{bmatrix}w&-y\\-z&x \end{bmatrix} = \begin{bmatrix}1&b\\0&1 \end{bmatrix}

    direct computation of the LHS shows that:

    \begin{bmatrix}wx&ax^2\\az^2&wx \end{bmatrix} = \begin{bmatrix} 1&b\\0&1 \end{bmatrix}

    so wx = 1, and z = 0, which in turn implies w = x = 1, and y can be arbitrary. the matrix:

    C = \begin{bmatrix}-1&-1\\0&-1 \end{bmatrix}

    has order 6, and <C> contains all such matrices (verification left to the reader). hence N(T) has order 6, and is cyclic. since SL(2,Z) has a unique element of order 2, so does SL(2,Z3).

    it can be shown that the number of distinct conjugates of a subgroup is the index of the normalizer of that subgroup, since [SL(2,Z3):N(T)] = 24/6 = 4, T has four distinct conjugates in SL(2,Z3)., say:

    T1,T2,T3,T4. this yield 4 distinct normalizers N(T1),N(T2),N(T3),N(T4).

    this accounts for 18 elements of SL(2,Z3), 6 in N(T1), and then 12 more from the other normalizers (each of which share the unique elements of orders 1 and 2).

    so what are the orders of the other 6 elements?

    well, note that:

    A = \begin{bmatrix}0&-1\\1&0 \end{bmatrix};\ B = \begin{bmatrix}-1&-1\\-1&1 \end{bmatrix}

    both have order 4, and that A2 = B2 = -I. calculations show AB is a 3rd matrix of order 4, so that our last 6 elements A,B,-A,-B,AB and -AB are all of order 4.

    this means the only possible orders of an element of SL(2,Z) are 1,2,3,4 and 6. we're almost there. we just need one more lemma:

    lemma #3: if A in GL(2,Z) has order > 2, A is in SL(2,Z).

    we saw before, that if the order of A is greater than 2, that the eigenvalues of A cannot be real, and are complex conjugates λ,λ*. but det(A) = (λλ*) = |λ| ≥ 0, and since det(A) = 1,

    we conclude that det(A) = 1, that is A is in SL(2,Z).

    hence the only possible orders for A are: 1,2,3,4 and 6, and each of these actually does occur.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Integer Valued Matrix
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: December 15th 2010, 07:56 PM
  2. Replies: 13
    Last Post: August 3rd 2010, 03:16 AM
  3. Integer roots of integer polynomials
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 3rd 2009, 12:39 PM
  4. Raise integer to positive integer power
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 21st 2009, 12:20 PM
  5. [SOLVED] even integer and odd integer
    Posted in the Algebra Forum
    Replies: 2
    Last Post: October 1st 2008, 08:35 PM

Search Tags


/mathhelpforum @mathhelpforum