Register to reply

2x2 matrix with factor group elements

by jostpuur
Tags: elements, factor, matrix
Share this thread:
jostpuur
#1
Aug27-14, 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.
Phys.Org News Partner Mathematics news on Phys.org
Math journal puts Rauzy fractcal image on the cover
Heat distributions help researchers to understand curved space
Professor quantifies how 'one thing leads to another'
Stephen Tashi
#2
Aug28-14, 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?
Incnis Mrsi
#3
Sep4-14, 01:42 PM
Incnis Mrsi's Avatar
P: 59
Quote Quote by Stephen Tashi View Post
Giving the problem a technical name, I'd called it "solving simultaneous linear equations in a finite field".
What? Original poster didnít say N must be prime. One can solve linear systems over rings with zero divisors (Ī mean ℤN for composite N), but it is a theory different from linear algebra over a field. Even solving one linear equation is a non-trivial problem since we, in general, canít divide.


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 non-trivial 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