0

What is the program (in MATLAB) which has an answer to the following question.

Let $p$ be a prime number and $n$ be a natural number. We are just supposed to focus on $M_n(Z_p)$, the set of $n\times n$ matrices with entries in the field $Z_{p}$.

Definition. We say that a matrix $A$ is $k$-positive if there are matrices $X_1,\cdots,X_k$ in $M_n(Z_{p})$ with $A=X_1^tX_1+\cdots+X^t_kX_k$ ($X^t$ is the transpose of $X$).

Problem. List all (pairwise different) $k$-positive matrices where $k=1,2,\cdots$.

Jean Marie
  • 81,803
ABB
  • 1,998
  • What are your thoughts and what have you tried...? There are only finitely many matrices in $M_n(Z_p)$ so you could do everything by brute force (might take a while for large $p,k,n$ though). – Surb May 04 '17 at 07:28
  • @Surb Could you please make more clarify? brute force?! – ABB May 04 '17 at 07:35
  • Well, you can list all matrices in $M_{n}(Z_p)$, and then list all matrices which are $k$-positive. Finally, you can clean the duplicates. But this is combinatorially slow. – Surb May 04 '17 at 07:42
  • You will have $p^{n^2}$ elements in $M_n(Z_p)$ and then at most $\binom{p^{n^2}}{k}$ possible $k$-positive matrices. So you can build them, take these constructions modulo $p$ and clean the duplicates. – Surb May 04 '17 at 07:45
  • Thanks for your hint but I think the program would not be straightforward! Since as for $k$-positive matrices, we have to consider any arbitrary $k$-tuple matries $X_1,\cdots,X_k$. – ABB May 04 '17 at 07:50
  • well, it is straightforward, but very very slow. – Surb May 04 '17 at 08:27

0 Answers0