About Cayley graphs on finite fields.

• If one is given $n$ vectors of length $n$ $\in \mathbb{F}_{p^k}^n$ for some prime number $p$ and $k \in \mathbb{Z}^+$ then how can one check if they are linearly independent? (the issue is if there are some short-cuts or algorithm to do this checking given the restriction of being on fields)

Given any such $n$ linearly independent vectors inside some $\mathbb{F}_{p^k}^n$, one can think of them as giving a basis of the vector space $\mathbb{F}_{p^k}^n$ over $\mathbb{F}_{p^k}$. Now I consider the Cayley graph on the group $\mathbb{F}_{p^k}^n$ (Abelian group under addition modulo $p$) with these $n$ vectors and their inverses) as generators.

Let $S$ be a basis of $\mathbb{F}_{p^k}^n$ over $\mathbb{F}_{p^k}$. Now consider the undirected Cayley graph, $Cay(\mathbb{F}_{p^k}^n, S \cup S^{-1})$. Also consider the matrix $M$ which is formed by stacking together as its columns the vectors in $S$ (or of $S \cup S^{-1}$ ; whatever helps!)

• Now I am asking if there is some relation between $Spec( Cay(\mathbb{F}_{p^k}^n, S \cup S^{-1}) )$ and $Spec(M)$?

• Those $n$ vectors will only generate $\Bbb{F}_{p^k}^n$ as a vector space over $\Bbb{F}_{p^k}$. When $k>1$ they will not generate $\Bbb{F}_{p^k}^n$ as an abelian group, so you get a disconnected Cayley graph as Chris Godsil (+1) explained. – Jyrki Lahtonen Apr 9 '15 at 19:28
• @JyrkiLahtonen Can you kindly explain your point? I am not seeing where this $C_p^n$ stricture is coming from that Chris mentions below. – user6818 Apr 9 '15 at 19:32
• The additive group of $\Bbb{F}_{p^k}^n$ is isomorphic to that of $\Bbb{F}_{p}^{kn}$ so you need $kn$ vectors to generate it as an additive group. – Jyrki Lahtonen Apr 9 '15 at 19:35
• Yes. $\mathbb{F}_{p}^{kn}$ is of dimension $kn$ over $\mathbb{F}_p$. But isn't it of dimension $n$ over $\mathbb{F}_{p^k}$? Hence I thought that a basis of $n$ vectors over $\mathbb{F}_{p^k}$ should generate the Abelian group, $\mathbb{F}_{p^k}^n$. – user6818 Apr 9 '15 at 19:37
• AFAICT = As Far As I Can Think ? :D – user6818 Apr 9 '15 at 20:00

The standard way to determine the dimension of the span of a set of vectors over a finite field is to compute reduced row-echelon form. In general there is no short cut.

If you have a basis for a vector space $V$ over a finite field then you can construct a directed Cayley graph with vertex set $V$ by adding an arrow from $u$ to $v$ if $v-u$ is one of the basis vectors. Note that over a field of order $p_k$, all addition is modulo $p$, not $p^k$.

If $p^k=2$, the Cayley graph constructed in the previous paragraph will be the $n$-cube. The result does not depend on the choice of basis.

If $p^k>2$, the additive group generated by your basis has order $p^n$. So the Cayley "graph" will not be connected, and each connected component has size $p^n$ and will be a Cartesian power of directed cycles of length $p$. (The spectrum of the Cartesian product of $n$ copies of a graph consists of all possible sums $x_1+\cdots+x_n$, where the $x_i$'s run over the eigenvalues of the graph. So again the spectrum does not depend on the choice of basis.)

• (1) Let $S$ be a basis of the vector space $\mathbb{F}_{p^k}^n$ over $\mathbb{F}_{p^k}$. Then can't I talk of the undirected Cayley graph $Cay(\mathbb{F}_{p^k}^n, S \cup S^{-1})$? (where I have symmetrized the generating set) Are you saying that this graph is disconnected? – user6818 Apr 9 '15 at 19:17
• (2) Now consider the matrix $M$ which is formed by stacking the vectors in $S$ (or of $S \cup S^{-1}$ - whatever helps!) as columns. I am asking if there is a relation between the $Spec(M)$ and $Spec(Cay(\mathbb{F}_{p^k}^n, S \cup S^{-1}))$ ? Like can the spectral gap of the later be seen by something in $M$? – user6818 Apr 9 '15 at 19:22
• @user6818: Well you could symmetrize the connection set, but I had to deal with what you wrote the first time. If you do symmetrize, you get a Cartesian power of cycles $C_p$, and the spectrum is still independent of the choice of basis. – Chris Godsil Apr 9 '15 at 19:27
• Sorry for that confusion! I have now edited to make that explicit. Surely the spectrum of the Cayley graph thus obtained is independent of the choice of basis but can I say something about that spectrum or its spectral gap from knowing about $M$? (at least if $p^k =2$?) ? Can you explain why this Cayley graph should be $C_p^n$? What is the natural choice of generating set which will give me a connected Cayley graph over $\mathbb{F}_{p^k}^n$? – user6818 Apr 9 '15 at 19:30
• @user6818: You can say something about the spectrum - you are dealing with a known graph and you can write down the eigenvalues explicitly. If your connection set is closed under multiplication by $-1$ and spans $V$, you will get a connected Cayley graph. Note that Cayley graphs for abelian groups cannot have a large spectral gap though. – Chris Godsil Apr 9 '15 at 19:36