mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Number Theory Discussion Group (https://www.mersenneforum.org/forumdisplay.php?f=132)

 bhelmes 2022-07-20 14:07

rotation matrix

A peaceful night for you,

the weather in Germany was yesterday and today a little bit hot,
which is not ideal for me to think about math.
Normally I prefer a temperature under 25 degree in the night.

I had to stop mprime and switch off my computer.

Let p:=31, a:=4+5i, b:=8+15i with 4²+5²=8²+15²=10 mod p
this means for me, that both gaussian numbers have a same norm,
which is not the same as the euklid norm.

Is there a rotation matrix R with det(R)=1 which transform a=R*b ?

:redface: :loco: :hello:

 Chris Card 2022-07-21 14:24

[QUOTE=bhelmes;609904]A peaceful night for you,

the weather in Germany was yesterday and today a little bit hot,
which is not ideal for me to think about math.
Normally I prefer a temperature under 25 degree in the night.

I had to stop mprime and switch off my computer.

Let p:=31, a:=4+5i, b:=8+15i with 4²+5²=8²+15²=10 mod p
this means for me, that both gaussian numbers have a same norm,
which is not the same as the euklid norm.

Is there a rotation matrix R with det(R)=1 which transform a=R*b ?

:redface: :loco: :hello:[/QUOTE]
[SPOILER]23 -12
25 -13[/SPOILER]
?

 bhelmes 2022-07-23 06:23

[SPOILER]23 -12
25 -13[/SPOILER]
?[/QUOTE]

There is a logical error in my thinking and I could not solve the paradox :

a:=4+5i, b:=8+15i
If I regard the euklidean norm of both vectors:
||a||=sqrt (16+25)=sqrt (41)
||b||=sqrt (64+225)=sqrt (289)
and I could not reduce it mod p, because there is the sqrt.
As the euklidean norm is not the same, there could not be a rotation matrix with det (R)=1,
which conserves the length of the vector.

If I regard the norm as ||a||:=16+25=41 and ||b||:=64+225=289 I could operate with mod p,
and both vectors are set on the same circle and there exist a rotation matrix,
as indicated above.

Strange. Any ideas where the logical error is hidden ?

 Chris Card 2022-07-25 12:20

[SPOILER][/SPOILER][QUOTE=bhelmes;610077]There is a logical error in my thinking and I could not solve the paradox :

a:=4+5i, b:=8+15i
If I regard the euklidean norm of both vectors:
||a||=sqrt (16+25)=sqrt (41)
||b||=sqrt (64+225)=sqrt (289)
and I could not reduce it mod p, because there is the sqrt.
As the euklidean norm is not the same, there could not be a rotation matrix with det (R)=1,
which conserves the length of the vector.

If I regard the norm as ||a||:=16+25=41 and ||b||:=64+225=289 I could operate with mod p,
and both vectors are set on the same circle and there exist a rotation matrix,
as indicated above.

Strange. Any ideas where the logical error is hidden ?

The matrix I gave has determinant 1, but is it a rotation matrix?
Not as a matrix over the integers certainly.
A square matrix R is a rotation matrix if and only if transpose(R) = inverse(R) and det R = 1.
[URL]https://en.wikipedia.org/wiki/Rotation_matrix[/URL]
It doesn't appear to be a rotation matrix mod 31 either - sorry :(
But I think this is
[SPOILER]
20 2
-2 20
[/SPOILER]
Chris

 Dr Sardonicus 2022-07-26 13:59

A "norm" is usually defined as being positive-definite, which makes no sense in modulo arithmetic.

Fortunately, what we're dealing with is a vector space over a field (the finite field of the integers modulo p, where p is a prime number). The usual formulas for matrix multiplication and inner product apply; but the results are integers modulo p rather than real numbers. But the definition of a "rotation matrix" (a square matrix [b][color=red] with determinant 1[/color][/b] whose inverse equals its transpose) still makes sense.

There is a straightforward solution to the stated problem, based on a well known formula for multiplying two expressions which are the sum of two squares. This formula is

(A^2 + B^2)*(C^2 + D^2) = (A*C ± B*D)^2 + (A*D ∓ B*C)^2

Suppose that p is a prime number, n (mod p) is a non-zero residue, and we have

a^2 + b^2 == n (mod p) and c^2 + d^2 == n (mod p).

The above formula gives

(a*c ± b*d)^2 + (a*d ∓ b*c)^2 == n^2 (mod p)

Dividing through by n^2 (which uses the hypothesis that n (mod p) is non-zero) gives

((a*c ± b*d)/n)^2 + ((a*d ∓ b*c)/n)^2 == 1 (mod p)

That is, for either choice of signs we have a pair (x, y)

x^2 + y^2 == 1 (mod p)

We also have

[b]a*(a*c + b*d) - b*(a*d - b*c) = (a^2 + b^2)*c, and

b*(a*c + b*d) + a*(a*d-b*c) = (a^2 + b^2)*d.

Thus, we have, with n = a^2 + b^2 = c^2 + d^2, x = (a*c + b*d)/n and y = (a*d - b*c)/n,

with the 2x2 matrix

M = [x, -y; y, x],

M[a;b] = [c;d] (the determinant is x^2 + y^2 = 1, and the inverse is equal to the transpose).[/b]

In the case at hand, taking a = 8, b = 15, c = 4, and d = 5 (mod 31) these formulas give

M = [20;2;-2;20] (mod 31).

(Here, I am using the Pari-GP convention that the entries in a row are separated by commas, and the rows are separated by semicolons.)

[b]Note:[/b] I had to rewrite the section in bold. I had the right approach, but transposing things and minus signs are among the banes of my existence. I fixed up the details, and made the appropriate revisions.

 Dr Sardonicus 2022-07-29 13:38

It occurred to me to wonder about using rotation matrices as an alternate approach to the well known - and long settled - question of counting solutions to a^2 + b^2 == k (mod p) where p is an odd prime.

A standard approach uses Gauss and Jacobi sums to count the number of solutions. It gives the exact answer in the quadratic case, and a good estimate for higher exponents. The rotation matrix method, alas, does not apply to higher exponents.

However, it actually does work in the quadratic case. It uses only very basic facts. One is that, if p is a prime number, the non-zero residues (mod p) form a multiplicative group which is cyclic of order p-1.

It follows that, if p is an odd prime, there is a multiplicative subgroup of order 4 when p == 1 (mod 4), but not if p == 3 (mod 4). That is, there are square roots of -1 (mod p) if p == 1 (mod 4) but not if p == 3 (mod 4).

A cyclic group of order g has cyclic subgroups of every order dividing g. In particular, when p is an odd prime, the multiplicative group of non-zero residues is cyclic of order p-1, so has a cyclic subgroup of order (p-1)/2. The elements of this subgroup are the non-zero quadratic residues (mod p), which we will denote by R. We have R == t^2 (mod p) for some non-zero t for each such R. The other (p-1)/2 non-zero residues (mod p) are the quadratic non-residues, which we will denote by N.

We now look at the equation a^2 + b^2 == k (mod p). Assuming there is a solution, we can multiply through by any quadratic residue R == t^2 (mod p), giving (a*t)^2 + (b*t)^2 == k*R (mod p).

So, the existence of solutions to a^2 + y^2 = k can depend at most on whether k is a quadratic residue. For k = 1, we have the solution 1^2 + 0 = 1, so there is a solution for k = R, R any quadratic residue.

Further, if R == t^2 (mod p), there is a solution for R + 1, namely t^2 + 1^2 == R + 1 (mod p).

Now R + 1 can't be a quadratic residue for every quadratic residue R, because if it were, every residue (mod p) would be a quadratic residue, and there are only (p-1)/2 quadratic residues.

Thus, there is at least one quadratic residue R (mod p) for which R + 1 = N, a quadratic non-residue (mod p), and for such an N, a^2 + b^2 = N has a solution (mod p). It follows that a^2 + b^2 = k (mod p) has a solution for every non-zero residue k (mod p).

This leaves the case of 0 (mod p). If p == 3 (mod 4) the only solution to a^2 + b^2 == 0 (mod p) is (a, b) = (0, 0). if p == 1 (mod 4), however, there are other solutions. There are two solutions to x^2 + 1 == 0 (mod p) [the two generators of the multiplicative subgroup of order 4]. Multiplying through by b^2 (mod p) for the p - 1 non-zero residues (mod p) then gives 2*p - 2 solutions to a^2 + b^2 == 0 (mod p) with (a,b) ≠ (0,0). So for p == 1 (mod 4) there are 2*p - 1 pairs (a, b) (mod p) for which a^2 + b^2 == 0 (mod p).

Now - finally! - here come the rotation matrices! From a previous post, we have a formula for a rotation matrix M = [x, -y;y, x] with det(M) = x^2 + y^2 = 1, that transforms

(a, b) with a^2 + b^2 = k (mod p) into

(c, d) with c^2 + d^2 = k (mod p)

by M[a;b] = [c;d]

We now show that if (a,b) ≠ (0, 0), the rotation matrix M is unique. Suppose that M and M' are rotation matrices for which M'[a;b] = M[a;b]. Then M[sup]-1[/sup]M'[a;b] = [a;b].

Now it is easily seen that the product of two rotation matrices is a rotation matrix (in fact, rotation matrices form a multiplicative group), so we can write

[x,-y;y;x][a;b] = [a;b] where x^2 + y^2 = 1 and [x,-y;y,x] = M[sup]-1[/sup]M'. We then have

[x-1,-y;y,x-1][a;b] = [0;0].

Since (a,b) ≠ (0, 0) this is only possible if the determinant of [x-1,-y;y,x-1] is 0. This determinant is (x-1)^2 + y^2 = x^2 + y^2 + 1 - 2*x = 2 - 2*x, since x^2 + y^2 = 1. Thus, x = 1 and y = 0, so M[sup]-1[/sup]M' is the 2x2 identity matrix; that is, M' = M. Thus, the rotation matrix M is unique.

It follows that the number of solutions to a^2 + b^2 == k (mod p) is the same for every non-zero residue k, and that this number (call it m) is equal to the number of solutions to x^2 + y^2 == 1 (mod p).

There are p^2 pairs of residues (a, b) (mod p). There are p-1 non-zero residues (mod p).

We showed earlier that if p == 3 (mod 4) there is one pair, (a, b) = (0,0) (mod p) for which a^2 + b^2 == 0 (mod p). In this case we have m*(p-1) + 1 = p^2, giving m = p+1.

If p == 1 (mod 4) we showed that there are 2*p - 1 pairs (a, b) (mod p) for which a^2 + b^2 == 0 (mod p). In this case we have m*(p-1) + 2*p - 1 = p^2, giving m = p-1.

 bhelmes 2022-08-20 01:18

A peaceful and pleasant night for you,

this is a beautiful and colored representation of numbers with the according rotation matrixs.
It is not perfect, but I thought LaurV or Serge could use them and will be happy about it:

[URL]http://devalco.de/unit_circle/system_tangens.php?prim=31[/URL]

Greetings from Germany

:gah::petrw1::juggle:

 bhelmes 2022-09-17 01:02

Basic rotation matrixes

A peaceful night for you, where ever you sleep,

Are there [B]three basic rotation[/B] [B]matrices[/B], like

E =
(1 0) = Identity with determinant (E) = 1
(0 1)

M1 =
(1 -1) with determinant (M1) = 2
(1 1)

and M2 =
(1 1) with determinant (M2) = 2
(-1 1)

and all resulting rotation matrices a[B] product of two scalars and the basic matrices[/B], so that det (M)=1 mod p ?
[B]
Example:[/B]
p=31

v1=2+3i
v2=5+9i
v3=4+11i
v4=6+15i

norm (v1) = 2²+3² = 13 = 12⁻¹ mod 31
norm (v2) = 5²+9² = 13 = 12⁻¹ mod 31
norm (v3) = 4²+11² = 13 = 12⁻¹ mod 31
norm (v4) = 6²+15² = 13 = 12⁻¹ mod 31

12*5*
(2,1)*(2)=(5)
(-1,2) (3)=(9)

12*27*
(1,1)*(2)=(5)
(-1,1) (3)=(9)

12*2*
(1,10)*(2)=(5)
(-10,1) (3)=(9)

:smile::cool::cmd::hello:

[url]http://devalco.de/unit_circle/system_tangens.php[/url]

P.S. I made a contract for 35 cent / kwh up to 31.10. which will enable my work for Gimps.

 Dr Sardonicus 2022-09-17 22:14

[QUOTE=bhelmes;613571]A peaceful night for you, where ever you sleep,

Are there [B]three basic rotation[/B] [B]matrices[/B], like

E =
(1 0) = Identity with determinant (E) = 1
(0 1)

M1 =
(1 -1) with determinant (M1) = 2
(1 1)

and M2 =
(1 1) with determinant (M2) = 2
(-1 1)

and all resulting rotation matrices a[B] product of two scalars and the basic matrices[/B], so that det (M)=1 mod p ?
<snip>[/QUOTE]A rotation matrix has determinant 1 by definition, so M1 and M2 are not rotation matrices.

If p is an odd prime, we have seen that if p == 3 (mod 4) there are p+1 rotation matrices (mod p), and if p == 1 (mod 4) there are p-1 rotation matrices (mod p).

I note that the rotation matrix [0,1;-1,0] has multiplicative order 4, proving that the group of rotation matrices (mod p) always has order divisible by 4.

I checked for 2 < p < 200 and found that the group of rotation matrices (mod p) was always cyclic. I'm convinced this is always the case, but don't presently see how to prove it.

I give cyclic generators for 2 < p < 100

p, group order, cyclic generator.
[code]3 4 [Mod(0, 3), Mod(1, 3); Mod(2, 3), Mod(0, 3)]
5 4 [Mod(0, 5), Mod(1, 5); Mod(4, 5), Mod(0, 5)]
7 8 [Mod(2, 7), Mod(2, 7); Mod(5, 7), Mod(2, 7)]
11 12 [Mod(3, 11), Mod(5, 11); Mod(6, 11), Mod(3, 11)]
13 12 [Mod(2, 13), Mod(6, 13); Mod(7, 13), Mod(2, 13)]
17 16 [Mod(4, 17), Mod(6, 17); Mod(11, 17), Mod(4, 17)]
19 20 [Mod(3, 19), Mod(7, 19); Mod(12, 19), Mod(3, 19)]
23 24 [Mod(4, 23), Mod(10, 23); Mod(13, 23), Mod(4, 23)]
29 28 [Mod(5, 29), Mod(11, 29); Mod(18, 29), Mod(5, 29)]
31 32 [Mod(2, 31), Mod(11, 31); Mod(20, 31), Mod(2, 31)]
37 36 [Mod(2, 37), Mod(16, 37); Mod(21, 37), Mod(2, 37)]
41 40 [Mod(13, 41), Mod(18, 41); Mod(23, 41), Mod(13, 41)]
43 44 [Mod(3, 43), Mod(11, 43); Mod(32, 43), Mod(3, 43)]
47 48 [Mod(4, 47), Mod(19, 47); Mod(28, 47), Mod(4, 47)]
53 52 [Mod(5, 53), Mod(20, 53); Mod(33, 53), Mod(5, 53)]
59 60 [Mod(11, 59), Mod(23, 59); Mod(36, 59), Mod(11, 59)]
61 60 [Mod(2, 61), Mod(27, 61); Mod(34, 61), Mod(2, 61)]
67 68 [Mod(3, 67), Mod(27, 67); Mod(40, 67), Mod(3, 67)]
71 72 [Mod(13, 71), Mod(20, 71); Mod(51, 71), Mod(13, 71)]
73 72 [Mod(6, 73), Mod(29, 73); Mod(44, 73), Mod(6, 73)]
79 80 [Mod(2, 79), Mod(32, 79); Mod(47, 79), Mod(2, 79)]
83 84 [Mod(3, 83), Mod(18, 83); Mod(65, 83), Mod(3, 83)]
89 88 [Mod(13, 89), Mod(30, 89); Mod(59, 89), Mod(13, 89)]
97 96 [Mod(14, 97), Mod(22, 97); Mod(75, 97), Mod(14, 97)][/code]

 bhelmes 2022-09-18 23:23

[QUOTE=Dr Sardonicus;613599]
A rotation matrix has determinant 1 by definition, so M1 and M2 are not rotation matrices.
[/QUOTE]
Every matrix M of the form
[B](x -y)
(y x)[/B]
with determinant (M)=x²+y² can be [B]transformed by a scalar multiplication of the matrix[/B] by the [B]inverse of the determinant[/B]
into [B]a rotation matrix with determinant 1[/B],

the determinant (M)=2 has an strong advantage, if the calculation is made modulo a Mersenne number.

As the 3 rotation matrices are calculated by 4 vectors of the same norm,
the belonging rotation matrices seem to build a connection between f(x)=x²+1 and g(x)=x²+x+1.

If I have one vector (a, bi) with the norm d=a²+b², I am only interesting in one rotation matrix,
with which I could find the rational point on the same circle with the radius of the norm.

I thought that
d*e*M1 with d=a²+b² and e well chosen so that det (d*e*M1)=1 should be one solution.

This was more than a brainstorm as exact mathematical explication,
but I think the Romulan Translator will get the idea,
and perhaps some more sophisticated Mathematicians will get the idea, too.

Sorry if the mathematical correctness suffers from the speed of ideas.

:cmd: :razz: :redface: :whistle:I

I tried to calculate the belonging matrices, and the red ones (non quadratic residues) are the interesting part.
[URL]http://devalco.de/unit_circle/system_tangens.php[/URL]

There may be some stupid programming errors and I beg pardon for it.
Perhaps I have missed some - or symmetrical axes.

 Dr Sardonicus 2022-09-19 21:56

[QUOTE=bhelmes;613648]Every matrix M of the form
[B](x -y)
(y x)[/B]
with determinant (M)=x²+y² can be [B]transformed by a scalar multiplication of the matrix[/B] by the [B]inverse of the determinant[/B]
into [B]a rotation matrix with determinant 1[/B]
<snip>[/QUOTE]No, sir. If M is a 2x2 matrix, scalar multiplication of M by k produces a matrix with determinant k^2*det(M). Thus, if M is a nonsingular 2x2 matrix, det((1/det(M))M) is 1/det(M).

If M is 2x2 and det(M) is not a square, no scalar multiple of M will have determinant 1.

Meanwhile, I have devised a proof that the group of 2x2 rotation matrices (mod p), AKA the "special orthogonal group" SO(2) over F[sub]p[/sub] is cyclic.

The order of the group is n = p+1 when p == 3 (mod 4) and n = p-1 when p == 1 (mod 4).

Note that if a^2 + b^2 == 1 (mod p), the characteristic polynomial of the rotation matrix M = [Mod(a,p), Mod(b,p);Mod(-b,p),Mod(a,p)] is x^2 - 2*a*x + 1 (mod p). The multiplicative order of M is n when the characteristic polynomial divides the cyclotomic polynomial of primitive nth roots of unity (mod p).

Note that, if p == 3 (mod 4) we have p = n-1, so the cyclotomic polynomial splits into quadratic factors. Calling one of these x^2 - 2*a*x + 1 (mod p) we see that the discriminant 4*a^2 - 4 is not a square (mod p). Since p == 3 (mod 4), we have that 4 - 4*a^2 is a square (mod p), so that 1 - a^2 is a square (mod p). If p == 1 (mod 4) we have p = n+1 so the cyclotomic polynomial splits into linear factors (mod p). Forming a quadratic using two reciprocal roots, we again have a quadratic x^2 - 2*a*x + 1. Because the quadratic is the product of two linear factors, the discriminant 4*a^2 - 4 is a square (mod p). Since here p == 1 (mod 4), -1 is a square (mod p), so that 4 - 4*a^2 is also a square (mod p), and so 1 - a^2 is a square (mod p).

Thus, in either case an a and b to form a rotation matrix of multiplicative order n can always be found. The following simple Pari-GP script produces cyclic generators M for odd primes less than 100.

[code]{
forprime(p=3,100,
if(p%4==3,
n=p+1;
F=factormod(polcyclo(n),p);
a=-polcoeff(F[1,1],1,x)/2;
N=factor(x^2-1+a^2);
b=polcoeff(N[1,1],0,x);
M=[a,b;-b,a];
print(p" "M)
,
n=p-1;
F=factormod(polcyclo(n),p);
r=-polcoeff(F[1,1],0,x);
a=(r+1/r)/2;
N=factor(x^2-1+a^2);
b=polcoeff(N[1,1],0,x);
M=[a,b;-b,a];
print(p" "M)
);
)
}
3 [Mod(0, 3), Mod(1, 3); Mod(2, 3), Mod(0, 3)]
5 [Mod(0, 5), Mod(1, 5); Mod(4, 5), Mod(0, 5)]
7 [Mod(2, 7), Mod(2, 7); Mod(5, 7), Mod(2, 7)]
11 [Mod(3, 11), Mod(5, 11); Mod(6, 11), Mod(3, 11)]
13 [Mod(2, 13), Mod(6, 13); Mod(7, 13), Mod(2, 13)]
17 [Mod(4, 17), Mod(6, 17); Mod(11, 17), Mod(4, 17)]
19 [Mod(16, 19), Mod(7, 19); Mod(12, 19), Mod(16, 19)]
23 [Mod(10, 23), Mod(4, 23); Mod(19, 23), Mod(10, 23)]
29 [Mod(6, 29), Mod(9, 29); Mod(20, 29), Mod(6, 29)]
31 [Mod(29, 31), Mod(11, 31); Mod(20, 31), Mod(29, 31)]
37 [Mod(8, 37), Mod(14, 37); Mod(23, 37), Mod(8, 37)]
41 [Mod(14, 41), Mod(16, 41); Mod(25, 41), Mod(14, 41)]
43 [Mod(20, 43), Mod(17, 43); Mod(26, 43), Mod(20, 43)]
47 [Mod(43, 47), Mod(19, 47); Mod(28, 47), Mod(43, 47)]
53 [Mod(12, 53), Mod(4, 53); Mod(49, 53), Mod(12, 53)]
59 [Mod(25, 59), Mod(5, 59); Mod(54, 59), Mod(25, 59)]
61 [Mod(14, 61), Mod(7, 61); Mod(54, 61), Mod(14, 61)]
67 [Mod(32, 67), Mod(7, 67); Mod(60, 67), Mod(32, 67)]
71 [Mod(33, 71), Mod(30, 71); Mod(41, 71), Mod(33, 71)]
73 [Mod(12, 73), Mod(21, 73); Mod(52, 73), Mod(12, 73)]
79 [Mod(77, 79), Mod(32, 79); Mod(47, 79), Mod(77, 79)]
83 [Mod(40, 83), Mod(12, 83); Mod(71, 83), Mod(40, 83)]
89 [Mod(28, 89), Mod(14, 89); Mod(75, 89), Mod(28, 89)]
97 [Mod(75, 97), Mod(14, 97); Mod(83, 97), Mod(75, 97)]
? [/code]

All times are UTC. The time now is 08:52.