Is there a function with these properties?

Question

I am looking for a function $\phi$ with the properties described below:

1. $\phi$ : $\mathbb{Z}_q^{n \times m} \rightarrow \mathbb{Z}_q^{n \times n}$.

2. $\phi(A) - \phi(B) \neq 0$ and is invertible if $A \neq B$

3. $\phi(A + B) = \phi(A) + \phi(B)$

Is there a function in literature or how can we design such a deterministic function which satisfies above properties?

Answer 1

The requirement $\phi(A) - \phi(B) \ne 0$ for $A \ne B$ is equivalent to $\phi$ being injective since $\phi(A) - \phi(B) \ne 0$ iff $\phi(A) \ne \phi(B)$.

But $\mathbb{Z}_q^{n \times m}$ has more elements than $\mathbb{Z}_q^{n \times n}$ because $m > n$. Hence no function $\phi : \mathbb{Z}_q^{n \times m} \to \mathbb{Z}_q^{n \times n}$ can be injective.

Answer 2

I cannot give a complete answer for $m \le n$, but only some partial results.

3. says that $\phi$ is a group homomorphism.

Under the presence of 3. we see that 2. is equivalent to

2'. $\phi(A)$ is invertible for $A \ne 0$.

If 2. is satisfied, then 2'. follows with $B = 0$. If 2'. is satisfied and $A \ne B$, then $A - B \ne 0$ and $\phi(A-B) = \phi(A) -\phi(B)$ is invertible (which implies of course $\phi(A) -\phi(B) \ne 0$).

Let us define $GL(n,\mathbb{Z}_q)$ to be the set of invertible $n \times n$-matrices over $\mathbb{Z}_q$. The required $\phi$ must then be an injective group homomorphism such that $\phi(\mathbb{Z}_q^{n \times m} \setminus \{ 0 \}) \subset GL(n,\mathbb{Z}_q)$ .

Case 1. $n = 1$. Then $m = 1$ and $\mathbb{Z}_q^{n \times m} = \mathbb{Z}_q^{n \times n} = \mathbb{Z}_q$. Hence $\phi$ exists if and only if $q$ is prime. If $q$ is prime, then $\phi = id$ will do, and if $p$ is not prime, then the number of invertible elements in $\mathbb{Z}_q$ is too small to allow an injection $\phi : \mathbb{Z}_q \to \mathbb{Z}_q$ (which automatically must be a bijection) such that $\phi(x)$ is invertible for $x \ne 0$.

Case 2. $n > 1$.

For $m = n$ there cannot exist $\phi$ as required because the number of invertible matrices is smaller than $q^{n^2} - 1$ so that the $q^{n^2} - 1$ elements of $\mathbb{Z}_q^{n \times n} \setminus \{ 0 \}$ cannot be mapped injectively to $GL(n,\mathbb{Z}_q)$.

In all other cases my knowledge about the rings $\mathbb{Z}_q$ and the associated matrix rings is not sufficient to give a definite answer. Some negative results will be availabe by counting the number of elements of $GL(n,\mathbb{Z}_q)$.

See What is the number of invertible $n\times n$ matrices in $\operatorname{GL}_n(F)$? for $q$ prime and Number of invertible matrices over finite rings for arbitrary $q$. This gives a necessary condition for the existence of $\phi$ - we must have $q^{n \cdot m} - 1 \le \#GL(n,\mathbb{Z}_q)$. This is certainly not sufficient because an arbitrary injection $\phi$ such that $\phi(\mathbb{Z}_q^{n \times m} \setminus \{ 0 \}) \subset GL(n,\mathbb{Z}_q)$ will not be a group homomorphism.

Edited: $\phi$ cannot exist if $q$ is not prime.

If $q$ is not prime, choose a nontrivial positive divisor $a$ of $q$. Let $[x]$ denote the equivalence class of $x$ in $\mathbb{Z}_q = \mathbb{Z}/q\mathbb{Z}$. For each $\xi \in \mathbb{Z}_q$ define $A(\xi) = (a_{ij}(\xi)) \in \mathbb{Z}_q^{n \times m}$ by $a_{ij}(\xi) = \xi$ for all $i,j$. Then $A(\xi) \ne 0$ for $\xi \ne 0$.

For any abelian group $G$, any $g \in G$ and any $n \in \mathbb{N}$ let $n \cdot g$ = sum of $n$ summands $g$. For $G = \mathbb{Z}_q$ we have $n \cdot \xi = [n] \xi$, and for $G = \mathbb{Z}_q^{n \times m}$ we have $n \cdot (a_{ij}) = (n \cdot a_{ij}) = ([n]a_{ij}) = [n](a_{ij})$.

Now assume $\phi$ exists. Then $\phi(A([x]))$ is invertible for all $x = 1, \dots,q-1$. But $A([a]) = A(a \cdot [1])) = a \cdot A([1]))$ , hence $\phi(A([a])) = a \cdot \phi(A([1])) = [a] \phi(A([1])) $. Let $X$ be an inverse of $\phi(A([a]))$. Then $I_n = \phi(A([a]))X = ([a] \phi(A([1])))X = [a] (\phi(A([1]))X)$. This means that each diagonal element $\delta_{ii}$ of $\phi(A([1]))X$ has the property $[a]\delta_{ii} =[1]$. Hence $[a]$ has an inverse in $\mathbb{Z}_q$ which is a contradiction because it is a zero divisor.