Matrix Square Roots over Finite FIelds.

[Syed]

Hi all,

I need to compute square roots of matrices defined over finite fields.

For matrices defined over reals/complex numbers one can find several algorithms.

In case of finite fields I am unable to find any [Tried SageMath also but no luck]

Any pointers on this will be very helpful.

Thanks,

Syed.

[Jitendra Kumar Kumawat]

Computing square roots of matrices over finite fields is indeed a challenging problem. Unlike over the reals or complex numbers, where you have a continuity that allows you to use various iterative methods and differential equations, finite fields have a very different structure.

Let's say you want to find a square root of a matrix `B`, i.e., a matrix `A` such that `A^2 = B`.

One way to approach the problem is to do it element-wise, i.e., for each element `b` of the matrix `B`, find an element `a` of the finite field such that `a^2 = b`. However, this only works if the matrix `B` is diagonalizable, and the square root of a diagonal matrix is another diagonal matrix with the square roots of the original matrix's elements on the diagonal.

This might not always be the case, and the general problem of finding matrix square roots over finite fields can be quite complicated.

However, you can attempt an approach using the Schur decomposition of a matrix. This would be a two-step process:

1. Compute the Schur decomposition of `B`. The Schur decomposition is a form of matrix decomposition which expresses a matrix `B` in the form `B = Q T Q^-1`, where `Q` is a unitary matrix and `T` is upper triangular. This decomposition always exists for any square matrix.

2. Compute the square root of the upper triangular matrix `T`. This can be done using a variation of the Newton method for square roots over the finite field. The main difficulty is dealing with the fact that the finite field doesn't have the same smoothness properties as the reals, so the convergence might not be as good, but it's still possible.

The square root of `B` would then be `Q sqrt(T) Q^-1`.

In terms of existing software, unfortunately, I am not aware of any specific library or tool that provides this functionality as of my training cut-off in September 2021. It's possible that newer software or libraries have been released since then. You might need to implement the above algorithm by yourself. As you've mentioned SageMath, it would likely be a good environment to do this in, as it supports both finite fields and matrix computations. Be sure to validate your implementation carefully, as algorithms over finite fields can be tricky to get right due to the lack of continuity and the peculiarities of finite field arithmetic.

--
You received this message because you are subscribed to the Google Groups "Macaulay2" group.
To unsubscribe from this group and stop receiving emails from it, send an email to macaulay2+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/macaulay2/11b25994-2fde-44b6-86ed-1a8c7d9be7b9n%40googlegroups.com.

[jche...@gmail.com]

If the size n of the matrices is not too large: one naive approach is to set up the system of n^2 quadrics in n^2 variables, and try to find rational points. Here's some proof-of-concept code (for which I make no claims regarding its optimization):

squareRootsMatrix = A -> (
n := numrows A;
x := getSymbol "x";
R := (ring A)(monoid[x_(1,1)..x_(n,n)]);
X := genericMatrix(R,n,n);
I := ideal(X^2 - A);
apply(select(minimalPrimes I, p -> degree p == 1), p -> X % p)
)

A = matrix{{4_(ZZ/11),-1,4,3,4,5},{0,5,1,5,-5,3},{0,0,-2,0,4,-3},{0,0,0,1,-5,1},{0,0,0,0,4,-1},{0,0,0,0,0,1}}
elapsedTime squareRootsMatrix A

Brief testing indicates practical runtimes up to size n = 6. Of course one can try and conjugate the input matrix A beforehand - generally, the sparser the better. (Note that not every matrix is similar to a triangular matrix - indeed, this happens if and only if the characteristic polynomial splits into (not necessarily distinct) linear factors over the field.)

Justin

[Jitendra Kumar Kumawat]

The proof-of-concept code you've provided seems to be written in the Macaulay2 software package, which is designed for computations in algebraic geometry and commutative algebra.

The general idea of the code is to find a square root of a given matrix. It does this by constructing an ideal in the ring of all n by n matrices (over the coefficient ring of A), where the ideal is generated by the entries of X^2 - A. Here, X is a generic matrix in that ring.

The square root of A is then found as a solution to this system of equations. Specifically, the code looks for minimal primes of the ideal that have degree 1, and for each such prime p, it computes X modulo p, which gives a possible square root of A.

The specific function you shared, squareRootsMatrix, finds the square roots of a given matrix using the above process.

As for the part about conjugating the input matrix A, you're referring to the idea of reducing the complexity of the input matrix to make the computation easier. In linear algebra, two matrices are said to be similar if they represent the same linear transformation with respect to possibly different bases. It's true that any matrix is similar to a triangular matrix if and only if its characteristic polynomial factors into linear terms over the field. However, over fields like the integers mod a prime, which might not be algebraically closed, the characteristic polynomial of a matrix might not factor into linear terms, so you can't always reduce a matrix to triangular form.

In terms of optimization, the main computational task is to compute the minimal primes of the ideal and to check their degrees. Depending on how Macaulay2 implements these tasks, there might be room for improvement. For example, it might be possible to avoid the need to compute all minimal primes, or to use a more efficient algorithm for checking their degrees. If you're interested in optimizing the code, you might want to look into the details of these computations.

As for the running time, it's difficult to say without knowing more about the internals of Macaulay2. The code is dealing with a system of n^2 equations in n^2 variables, so it's not surprising that the running time increases quickly with n. It's impressive that the code is practical up to n = 6. With further optimization, it might be possible to handle larger matrices.

Note: Macaulay2 uses 1-indexing, so x_(1,1) to x_(n,n) refers to a matrix of size n by n. Also, the elapsedTime function measures the time taken by the squareRootsMatrix function to compute. The matrix A is an example you have used for the test.

To view this discussion on the web visit https://groups.google.com/d/msgid/macaulay2/6731cb7e-4b87-4cef-ad26-a6101017360en%40googlegroups.com.

[jche...@gmail.com]

Thanks for the explanation of my code, ChatGPT!

Justin

[Syed]

Thanks to both Jitendra and Justin for your replies. 

Meanwhile I was able to find some interesting results on this problem.

The problem seems to be hard as mentioned earlier.  While there is no general theorem on the hardness I found

one paper which proves that the problem indeed is NP-complete for matrices defined over F2.  

see here: https://www.sciencedirect.com/science/article/pii/S0304397504004165

In fact, the result is much stronger: It says deciding if a square matrix over F2 has a nth root is NP complete.

I am interested in knowing if the result can be extended to matrices over other finite fields,  at least like F_{2^n}.

Another question I am interested in:  In general how many square roots does a matrix (over Fq) have?

Known:  If a mxm matrix has m distinct eigenvalues in Fq then it has 2^m square roots. [using diagonalisation].  This is a very strong condition and most of the times not satisfied, especially if the finite field is small like F2 or F3, F5.

Suppose we have a matrix A which  is not diagonalizable or has no Jordan form over Fq [assume q =2/3/5].   In that case
how to count [not compute]  the number of square roots of A [assuming that it has a square root]?     

Note that  if sqrt(A) = B then -B is also a square root. We are interested in counting the square roots modulo this relation.

Thanks in advance for your replies.

Regards,

Syed.