# Permutation and combination in matrices

Printable View

• September 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.
• September 15th 2012, 12:36 PM
johnsomeone
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}.
• September 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.
• September 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 $\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$.