20220720, 14:07  #1 
Mar 2016
110011010_{2} Posts 
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 ? 
20220721, 14:24  #2  
Aug 2004
7×19 Posts 
Quote:
23 12 25 13 ? Last fiddled with by Chris Card on 20220721 at 15:19 

20220723, 06:23  #3 
Mar 2016
19A_{16} Posts 
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 ? 
20220725, 12:20  #4  
Aug 2004
7·19 Posts 
Quote:
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. https://en.wikipedia.org/wiki/Rotation_matrix It doesn't appear to be a rotation matrix mod 31 either  sorry :( But I think this is 20 2 2 20 Chris Last fiddled with by Chris Card on 20220725 at 12:58 

20220726, 13:59  #5 
Feb 2017
Nowhere
43×139 Posts 
A "norm" is usually defined as being positivedefinite, 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 with determinant 1 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 nonzero 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 nonzero) 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 a*(a*c + b*d)  b*(a*d  b*c) = (a^2 + b^2)*c, and b*(a*c + b*d) + a*(a*db*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). 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 PariGP convention that the entries in a row are separated by commas, and the rows are separated by semicolons.) Note: 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. Last fiddled with by Dr Sardonicus on 20220727 at 13:58 Reason: Add omitted condition, and as indicated 
20220729, 13:38  #6 
Feb 2017
Nowhere
43×139 Posts 
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 nonzero residues (mod p) form a multiplicative group which is cyclic of order p1. 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 nonzero residues is cyclic of order p1, so has a cyclic subgroup of order (p1)/2. The elements of this subgroup are the nonzero quadratic residues (mod p), which we will denote by R. We have R == t^2 (mod p) for some nonzero t for each such R. The other (p1)/2 nonzero residues (mod p) are the quadratic nonresidues, 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 (p1)/2 quadratic residues. Thus, there is at least one quadratic residue R (mod p) for which R + 1 = N, a quadratic nonresidue (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 nonzero 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 nonzero 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^{1}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^{1}M'. We then have [x1,y;y,x1][a;b] = [0;0]. Since (a,b) ≠ (0, 0) this is only possible if the determinant of [x1,y;y,x1] is 0. This determinant is (x1)^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^{1}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 nonzero 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 p1 nonzero 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*(p1) + 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*(p1) + 2*p  1 = p^2, giving m = p1. Last fiddled with by Dr Sardonicus on 20220729 at 13:52 Reason: fignix topsy 
20220820, 01:18  #7 
Mar 2016
19A_{16} Posts 
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: http://devalco.de/unit_circle/system...ns.php?prim=31 Greetings from Germany 
20220917, 01:02  #8 
Mar 2016
19A_{16} Posts 
Basic rotation matrixes
A peaceful night for you, where ever you sleep,
Are there three basic rotation matrices, 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 product of two scalars and the basic matrices, so that det (M)=1 mod p ? Example: 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) http://devalco.de/unit_circle/system_tangens.php P.S. I made a contract for 35 cent / kwh up to 31.10. which will enable my work for Gimps. Last fiddled with by bhelmes on 20220917 at 01:04 
20220917, 22:14  #9  
Feb 2017
Nowhere
43×139 Posts 
Quote:
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 p1 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)] Last fiddled with by Dr Sardonicus on 20220917 at 22:15 Reason: Insert missing qualifier 

20220918, 23:23  #10  
Mar 2016
632_{8} Posts 
Quote:
(x y) (y x) with determinant (M)=x²+y² can be transformed by a scalar multiplication of the matrix by the inverse of the determinant into a rotation matrix with determinant 1, 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. I I tried to calculate the belonging matrices, and the red ones (non quadratic residues) are the interesting part. http://devalco.de/unit_circle/system_tangens.php There may be some stupid programming errors and I beg pardon for it. Perhaps I have missed some  or symmetrical axes. Last fiddled with by bhelmes on 20220918 at 23:25 

20220919, 21:56  #11  
Feb 2017
Nowhere
1759_{16} Posts 
Quote:
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_{p} is cyclic. The order of the group is n = p+1 when p == 3 (mod 4) and n = p1 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 = n1, 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 PariGP 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^21+a^2); b=polcoeff(N[1,1],0,x); M=[a,b;b,a]; print(p" "M) , n=p1; F=factormod(polcyclo(n),p); r=polcoeff(F[1,1],0,x); a=(r+1/r)/2; N=factor(x^21+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)] ? 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
2*2 Matrix with determinant 1  bhelmes  Number Theory Discussion Group  4  20220214 15:04 
pyth. trippel and rotation  bhelmes  Number Theory Discussion Group  5  20170817 21:12 
Connectivity Matrix  Xyzzy  Lounge  13  20170221 18:29 
12+256 matrix job  fivemack  Factoring  11  20090818 17:39 
GF(2) Matrix request  oslik  Factoring  22  20081102 12:53 