Register to reply 
2x2 matrix with factor group elements 
Share this thread: 
#1
Aug2714, 11:35 AM

P: 2,068

We fix some [itex]N=1,2,3,\ldots,[/itex] and define the factor group [itex]\mathbb{Z}_N[/itex] as [itex]\mathbb{Z}/N\mathbb{Z}[/itex], and denote the elements [itex]x+N\mathbb{Z}[/itex] as [itex][x][/itex], where [itex]x\in\mathbb{Z}[/itex]. My question is that how do you solve [itex][x_1][/itex] and [itex][x_2][/itex] out of
[tex] \left(\begin{array}{c} \lbrack y_1\rbrack \\ \lbrack y_2\rbrack \\ \end{array}\right) = \left(\begin{array}{cc} \lbrack a_{11}\rbrack & \lbrack a_{12}\rbrack \\ \lbrack a_{21}\rbrack & \lbrack a_{22}\rbrack \\ \end{array}\right) \left(\begin{array}{c} \lbrack x_1\rbrack \\ \lbrack x_2\rbrack \\ \end{array}\right) [/tex] when [itex][y_1],[y_2],[a_{11}],[a_{12}],[a_{21}],[a_{22}]\in\mathbb{Z}_N[/itex] are known constants. First edit: To clarify what I mean by "a solution", I'll show a one for the 1x1 case, where we seek to solve [itex][y]=[a][x][/itex]. If [itex][a]=0[/itex] and [itex][y]\neq 0[/itex], then there are no solutions. If [itex][a]=0[/itex] and [itex][y]=0[/itex], then all [itex][x]\in\mathbb{Z}_N[/itex] are solutions, and the number of different solutions is [itex]N[/itex]. If [itex][a]\neq 0[/itex], we choose representatives [itex]a,y\in\mathbb{Z}[/itex] such that [itex]0<a<N[/itex] and [itex]0\leq y<N[/itex]. If [itex]\textrm{gcd}(a,N)[/itex] does not divide [itex]y[/itex], then there are no solutions. If [itex]\textrm{gcd}(a,N)[/itex] divides [itex]y[/itex], then a solution exists, and the number of different solutions [itex][x]\in\mathbb{Z}_N[/itex] is [itex]\textrm{gcd}(a,N)[/itex]. So the solution is unique only if [itex]\textrm{gcd}(a,N)=1[/itex]. Above we interpret that if [itex]y=0[/itex], then [itex]\textrm{gcd}(a,N)[/itex] divides [itex]y[/itex]. The whole thing is surprisingly complicated, considering how simple the formula [itex][y]=[a][x][/itex] looks. So I would be expecting something similar, but more complicated for the 2x2 case. The greatest common divisor of [itex]a_{11}a_{22}  a_{12}a_{21}[/itex] with something is probably related to the solution? Of course the problem is not really to write down an algorithm that would "solve" the problem, because that would be trivial. We could write a program that goes through all the [itex]N^2[/itex] possibilities for [itex]([x_1],[x_2])[/itex], and checks which one of them work. I'm seeking something reasonably analytic. Second edit: I think I already realized how the problem gets solved, and I probably spent more time describing the problem than solving it, which is peculiar of course... I haven't solved the whole thing yet fully though. 


#2
Aug2814, 04:24 PM

Sci Advisor
P: 3,313

Giving the problem a technical name, I'd called it "solving simultaneous linear equations in a finite field".
A useful digression would be to ask: What's the rellation between the solutions to to simultaneous linear Diophantine equations and the soluitons to linear equations in a finite field? 


#3
Sep414, 01:42 PM

P: 59




Register to reply 
Related Discussions  
Trace of elements in a finite complex matrix group is bounded  Calculus & Beyond Homework  2  
Regarding a Group Theory Proof on the Order of Elements in a Group  Calculus & Beyond Homework  2  
Is a factor group by a nontrivial normal subgroup is always smaller than the group ?  Calculus & Beyond Homework  1  
Group/Representation Theory Help! (Summations and elements of a finite group)  Calculus & Beyond Homework  7  
Kronecker product on only a few elements in a matrix: How to align resulting elements  Linear & Abstract Algebra  0 