2
$\begingroup$
  • 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)$?

Related, Cayley graphs on small Dihedral and Cyclic group, Cayley graph on $ D_{2n} $ and $ \mathbb Z_n$, Cayley graphs of finite 2-generator groups

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Apr 9 '15 at 19:28
  • $\begingroup$ @JyrkiLahtonen Can you kindly explain your point? I am not seeing where this $C_p^n$ stricture is coming from that Chris mentions below. $\endgroup$ – user6818 Apr 9 '15 at 19:32
  • $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Apr 9 '15 at 19:35
  • $\begingroup$ 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$. $\endgroup$ – user6818 Apr 9 '15 at 19:37
  • 1
    $\begingroup$ AFAICT = As Far As I Can Think ? :D $\endgroup$ – user6818 Apr 9 '15 at 20:00
2
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ (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? $\endgroup$ – user6818 Apr 9 '15 at 19:17
  • $\begingroup$ (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$? $\endgroup$ – user6818 Apr 9 '15 at 19:22
  • $\begingroup$ @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. $\endgroup$ – Chris Godsil Apr 9 '15 at 19:27
  • $\begingroup$ 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$? $\endgroup$ – user6818 Apr 9 '15 at 19:30
  • $\begingroup$ @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. $\endgroup$ – Chris Godsil Apr 9 '15 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.