Results 1 to 4 of 4
Like Tree1Thanks
  • 1 Post By johnsomeone

Math Help - Permutation and combination in matrices

  1. #1
    Member
    Joined
    Jun 2009
    Posts
    77

    Permutation and combination in matrices

    Let p be an odd prime number and T be the following set of 2X2 matrices,
    T={A=matrix such that a11=a, a12=b, a21=c, a22=a where aij denotes the term in ith row and jth column
    a,b,c belongs to {0,1,2,........,p-1}
    THen number of A in T such that trace of A is not divisible by p but det(A) is divisible by p is?
    trace of matrix isthe sum of its diagnol entries.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: Permutation and combination in matrices

    Let A be any of these described matricies, A = \begin{pmatrix} a& b \\ c& a \end{pmatrix}.

    Then Tr(A) \nsim 0 \bmod p \Rightarrow 2a \nsim 0 \bmod p \Rightarrow a \nsim 0 \bmod p (since p is odd).

    And Det(A) \sim 0 \bmod p \Rightarrow a^2 - bc \sim 0 \bmod p \Rightarrow bc \sim a^2 \bmod p.

    Since a \nsim 0 \bmod p via the nonzero trace, clearly bc \nsim 0 \bmod p \Rightarrow b \nsim 0 \bmod p, and c \nsim 0 \bmod p.

    From that it's obvious to identify the given set of usable integers \{0, 1, 2, ... , (p-1) \} with \mathbb{Z}_p, the integer remainders modulo p.

    Let \mathbb{Z}_p^* = \mathbb{Z}_p - \{ 0 \}, and denote the multiplicative inverse of x \in \mathbb{Z}_p^* by x^*.

    So we want the cardinality of \mathcal{M} = \{ \begin{pmatrix} a& b \\ c& a \end{pmatrix} \in M_{2,2}(\mathbb{Z}_p) \ | \ a, b, c \in \mathbb{Z}_p^*, bc = a^2 \}.

    But bc = a^2 amounts to simply c = b^*a^2.

    Thus \mathcal{M} = \{ \begin{pmatrix} a& b \\ b^*a^2& a \end{pmatrix} \in M_{2,2}(\mathbb{Z}_p) \ | \ a, b \in \mathbb{Z}_p^* \}.

    Thus the function \mathbb{Z}_p^* \times \mathbb{Z}_p^* \rightarrow \mathcal{M}, (a,b) \mapsto \begin{pmatrix} a& b \\ b^*a^2& a \end{pmatrix}, is surjective.

    But looking at the first row shows it's obviously injective. Hence it's bijective.

    Hence |\mathcal{M}| = | \mathbb{Z}_p^* \times \mathbb{Z}_p^* | = |\mathbb{Z}_p^* |^2 = (p-1)^2.

    Thus there are (p-1)^2 disitinct matricies your problem described, exactly one such for each top row made by choosing any values in {1, 2, ..., p-1}.
    Last edited by johnsomeone; September 15th 2012 at 12:52 PM.
    Thanks from jashansinghal
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2009
    Posts
    77

    Re: Permutation and combination in matrices

    Thanks. But can you give a simpler proof. I am not pro at number theory.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: Permutation and combination in matrices

    There's nothing advanced there. Maybe some of the notation I used you weren't familiar with? (those funky twists in front of thosee "mod p" mean "congruent to". It's tempting to write "32 = 7 mod 5", but I suppose that mathematicians loathe to write, even when it makes sense, that 32 = 7, just on general principles. It's just easier to write congruence rather than equals, because otherwise they have to write it as "[32] = [7] in \mathbb{Z}_5", which is a pain. All it means is "modulo p" which means "remainders when dividing by p".

    I filled in almost all the details - that's the only real reason it seems long. To someone who I already knew was comfortable with math, my answer might've gone like this (or much much less - just writing down the form of the answer): (Note that this isn't a demonstration so much as an explanation):

    If \mathcal{M} represents those matricies, then obviously A \in \mathcal{M} \Rightarrow A = \begin{pmatrix} a& b \\ b^*a^2& a \end{pmatrix} \in M_{2,2}(\mathbb{Z}_p).

    You can quickly see that Det(A) = a^2 - (b^*a^2)(b) = a^2 - (a^2)(b^*b) = a^2 - a^2 = 0 as required.

    However, since Trace(A) = 2a isn't zero and p \ne 2, a \ne 0. Obviously b can't be zero, since its inverse is required.

    Because of the top row, each choice of pairs (a,b) \in (\mathbb{Z}_p-\{0\}) \times (\mathbb{Z}_p-\{0\}) gives a different matrix in \mathcal{M}.

    All the matricies of \mathcal{M} are obviously included.

    Thus |\mathcal{M}| = |(\mathbb{Z}_p-\{0\}) \times (\mathbb{Z}_p-\{0\})| = (p-1)^2.
    Last edited by johnsomeone; September 16th 2012 at 12:48 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Permutation and Combination
    Posted in the Statistics Forum
    Replies: 2
    Last Post: January 17th 2011, 04:35 AM
  2. Permutation or combination?
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: October 13th 2010, 05:31 PM
  3. Permutation and combination
    Posted in the Statistics Forum
    Replies: 2
    Last Post: February 16th 2010, 03:30 AM
  4. permutation and combination
    Posted in the Statistics Forum
    Replies: 3
    Last Post: February 4th 2009, 03:21 PM
  5. Permutation or Combination
    Posted in the Statistics Forum
    Replies: 3
    Last Post: December 21st 2006, 07:09 PM

Search Tags


/mathhelpforum @mathhelpforum