# Permutation and combination in matrices

• Sep 14th 2012, 08:02 AM
jashansinghal
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.
• Sep 15th 2012, 12:36 PM
johnsomeone
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}.
• Sep 15th 2012, 11:09 PM
jashansinghal
Re: Permutation and combination in matrices
Thanks. But can you give a simpler proof. I am not pro at number theory.
• Sep 16th 2012, 12:29 AM
johnsomeone
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$.