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

Thread: 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
    MHF Contributor
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    1,061
    Thanks
    410

    Re: Permutation and combination in matrices

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

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

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

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

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

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

    So we want the cardinality of $\displaystyle \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 $\displaystyle bc = a^2$ amounts to simply $\displaystyle c = b^*a^2$.

    Thus $\displaystyle \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 $\displaystyle \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 $\displaystyle |\mathcal{M}| = | \mathbb{Z}_p^* \times \mathbb{Z}_p^* | = |\mathbb{Z}_p^* |^2 = (p-1)^2$.

    Thus there are $\displaystyle (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; Sep 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
    MHF Contributor
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    1,061
    Thanks
    410

    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 $\displaystyle \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 $\displaystyle \mathcal{M}$ represents those matricies, then obviously $\displaystyle 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 $\displaystyle Det(A) = a^2 - (b^*a^2)(b) = a^2 - (a^2)(b^*b) = a^2 - a^2 = 0$ as required.

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

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

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

    Thus $\displaystyle |\mathcal{M}| = |(\mathbb{Z}_p-\{0\}) \times (\mathbb{Z}_p-\{0\})| = (p-1)^2$.
    Last edited by johnsomeone; Sep 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: Jan 17th 2011, 04:35 AM
  2. Permutation or combination?
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Oct 13th 2010, 05:31 PM
  3. Permutation and combination
    Posted in the Statistics Forum
    Replies: 2
    Last Post: Feb 16th 2010, 03:30 AM
  4. permutation and combination
    Posted in the Statistics Forum
    Replies: 3
    Last Post: Feb 4th 2009, 03:21 PM
  5. Permutation or Combination
    Posted in the Statistics Forum
    Replies: 3
    Last Post: Dec 21st 2006, 07:09 PM

Search Tags


/mathhelpforum @mathhelpforum