generalization of positive-definite matrices to matrices over finite fields

Question

Let $\mathbb{F}$ be a field, $\mathbb{F}^n$ be the $n$-dimensional vector space over $\mathbb{F}$, and $M_{n\times n}(\mathbb{F})$ be the space of $n\times n$ matrices with entries in $\mathbb{F}$. We want to find a subspace $G_{n\times n}(\mathbb{F})$ of $M_{n\times n}(\mathbb{F})$ such that for any $A\in G_{n\times n}(\mathbb{F})$ and any nonzero $v\in\mathbb{F}^n$, $v Av^{T}\neq 0$. Here $v^T$ is the transpose of the row vector $v$.

Case~1. Let $\mathbb{F}=\mathbb{R}$. Then we can choose $G_{n\times n}(\mathbb{F})$ as the collection of all positive definite matrices.

Case~2. Let $\mathbb{F}=\mathbb{Z}_p$ consisting of $p$-elements, where $p$ is a prime. Then how can we choose $G_{n\times n}(\mathbb{F})$?

Answer 1

Such a map $v\mapsto vAv^{T}$ defines a quadratic form on $\mathbb{F}^{n}$, and your desired property that for all $v \neq 0$, $vAv^{T}\neq0$ is that the quadratic form is anisotropic.

Basically, we define map $Q : \mathbb{F}^{n} \to \mathbb{F}$ by $Q(v) = v A v^{T}$. This map has the property that, if $a \in \mathbb{F}$, then $Q(av) = a^{2}Q(v)$ (this is why it is called a quadratic form). If we fix a basis $\{u_{1}, \ldots, u_{n}\}$ then we can define a matrix $B = [B_{ij}] = [\frac{1}{2}(Q(u_{i}+u_{j})-Q(u_{i})-Q(u_{j}))]$, this gives you another matrix with $Q(v) = vAv^{T} = vBv^{T}$, but $B$ is now symmetric. $B$ then defines a bilinear form $B(u,v) = uBv^{T}$ with $B(u,v) = B(v,u)$ for all $u,v \in \mathbb{F}^{n}$, which is used to define an orthogonality relation on $\mathbb{F}^{n}$ by $u \perp v \iff B(u,v) = 0$. We have the following useful Lemma.

Lemma: If $B$ is a nonzero symmetric matrix associated with the quadratic form $Q$, then there exists some $v$ with $Q(v) \neq 0$.

(Notice that by our formula for obtaining $B$ from $Q$, if $Q(v) = 0$ for all $v$ then $B = 0$.)

Furthermore, we can choose a basis relative to which $B$ is diagonal. I will include a slightly paraphrased proof due to Grove (in Classical Groups and Geometric Algebra):

Proof: We use induction on $n$. If $B=0$ then we are done, otherwise we choose $v_{1}$ with $Q(v_{1})=b_{1} \neq 0$, and set $W = \mathrm{Span}(v_{1})$. Now $\mathbb{F}^{n} = W \oplus W^{\perp}$ (orthogonal sum), now $W^{\perp}$ has dimension less than $n$ so by our inductive argument, $B$ restricted to $W$ can be represented by a diagonal matrix $\hat{B}^{\prime}$ giving us the following diagonal representation of $B$: $$\hat{B} = \begin{bmatrix}b_{1} & 0 \\0& \hat{B}^{\prime}\end{bmatrix}$$

Now, we want to show that if $n \geq 3$, then there will exist a $v \neq 0$ with $Q(v) = 0$. (Leaving this as a partial answer for the moment to jog Jyrki's memory on his proof, and because I have to work on other things for a few hours before I can come back to this.)

Answer 2

Supplementing Morgan's answer with the following.

Assume that $Q$ is a quadratic form on $n\ge3$ variables ranging over the field $\Bbb{F}_p,p>2$. By the result recalled by Morgan we know that $Q$ is of the form $$ Q(v)=\lambda_1v_1^2+\lambda_2v_2^2+\lambda_3v_3^2+\cdots+\lambda_n v_n^2. $$ I claim that for some vector $(v_1,v_2,v_3)\neq(0,0,0)$ from $\Bbb{F}_p^3$ we have $Q(v_1,v_2,v_3,0,0,\ldots,0)=0$. If any of $\lambda_1,\lambda_2,\lambda_3$ happens to vanish, this is trivially the case, so we can assume that $\lambda_1\lambda_2\lambda_3\neq0$. Recall that squaring $x\mapsto x^2$ is a 2-1 mapping from $\Bbb{F}_p^*$ to itself. Including $x=0$ we then see that each of the monomials $\lambda_ix^2$ takes $(p+1)/2$ distinct values when $x$ ranges over $\Bbb{F}_p$ - the value $0$ once and the $(p-1)/2$ non-zero values twice each.

Next we claim that the quadratic form $P(v_1,v_2)=\lambda_1v_1^2+\lambda_2v_2^2$ gives a surjective function from $\Bbb{F}_p^2$ to $\Bbb{F}_p$. To see this let us consider an arbitrary element $y\in\Bbb{F}_p$. Consider the sets $$ S_1=\{\lambda_1v_1^2\mid v_1\in\Bbb{F}_p\} $$ and $$ S_2=\{y-\lambda_2v_2^2\mid v_2\in\Bbb{F}_p\}. $$ We just saw that both sets $S_1$ and $S_2$ have $(p+1)/2$ elements. Because there are exactly $p$ elements in $\Bbb{F}_p$, and between them the two subsets have $p+1$ elements, the intersection $S_1\cap S_2$ must be non-empty. In other words there exists elements $v_1,v_2\in\Bbb{F}_p$ such that $$ \lambda_1v_1^2=y-\lambda_2v_2^2\implies y=P(v_1,v_2). $$

The main claim now follows easily. Let $v_3=1$. Then, by the previos observation we can find $v_1,v_2\in\Bbb{F}_p$ such that $P(v_1,v_2)=-\lambda_3=-\lambda_3\cdot1^2.$ Consequently $$ Q(v_1,v_2,1)=0. $$

---

It is also worth pointing out that when $n=2$ we do have anisotropic quadratic forms over $\Bbb{F}_p$. If we choose $a\in\Bbb{F}_p$ such that $-a$ is not a square in $\Bbb{F}_p$ (there are $(p-1)/2$ such choices for $a$), then the form $$ Q(v_1,v_2)=v_1^2+av_2^2 $$ vanishes only when $v_1=v_2=0$. This is because $Q(v_1,v_2)=0$ implies that $-a=(v_1/v_2)^2$. The best known case is that of $p\equiv-1\pmod4$, $a=1$. It has been a part of many a question on our site that the form $$ Q(x,y)=x^2+y^2 $$ has no non-trivial zeros for these choices of $p$.

---

The trick in proving that every element of $\Bbb{F}_p$ can written as a sum of two elements coming from subsets $A,B\subset\Bbb{F}_p$ such that $|A|+|B|>p$ has been seen on our site many times. Particularly when dealing with squares.

---

It may also be worth pointing out that when $p=2$ a quadratic form is really a linear form, because $x^2=x$ for all $x\in\Bbb{F}_2$. The theory of symmetric bilinear forms over $\Bbb{F}_2$ on the other hand is more interesting, and has many applications in coding theory.