2
  • 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

Community
  • 1
user6818
  • 1,325
  • 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 09 '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 09 '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 09 '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 09 '15 at 19:37
  • If $x_1,x_2,\ldots,x_n$ are the elements of your basis, the additive group they generate consists of those linear combinations $$a_1x_1+a_2x_2+\cdots+a_nx_n,$$ where all the coefficients $a_i$ are in the prime field $\Bbb{F}p$. You will miss all the linear combinations where one or more of the $a_i$:s are in $\Bbb{F}{p^k}\setminus \Bbb{F}_p$. – Jyrki Lahtonen Apr 09 '15 at 19:46
  • So now I wonder why this construction works : Take $m$ vectors in $\mathbb{F}_2^d$. Now define that there is a edge between two elements of $\mathbb{F}_2^d$ if they differ by any of these $m$ vectors. Then one gets a degree-$m$ regular Cayley graph for the group $\mathbb{F}_2^d$. Here I would think that these $m$ vectors give a generating set for the Cayley graph -right? Or are more conditions needed on these $m$ vectors to keep the above Cayley graph connected? And you say that these $m$ vectors don't have any natural relationship to a basis of $\mathbb{F}_2^d$ over $\mathbb{F}_2$? – user6818 Apr 09 '15 at 19:51
  • I didn't say that. The problem only appears when $k>1$. – Jyrki Lahtonen Apr 09 '15 at 19:53
  • For example take $p=k=2, n=1$. We have $\Bbb{F}_4={0,1,\alpha,1+\alpha}$ with $1+1=0=\alpha+\alpha$, $\alpha^2=1+\alpha$. As a vector space over $\Bbb{F}_4$ this is one-dimensional, so $S={1}$ is a basis. But the resulting graph has two connectivity components ${0,1}$ and ${\alpha.1+\alpha}$. You cannot reach one component from the other by adding (or subtracting which amouunts to the same) elements of $S$. – Jyrki Lahtonen Apr 09 '15 at 19:57
  • Ah! Okay! Now it makes a lot of sense! So I can always do the above for some $\mathbb{F}_p^n$? So I can always choose a $n$ sized basis $S$ of $\mathbb{F}_p^n$ over $\mathbb{F}_p$ and see them as giving me a connected Cayley graph $Cay(\mathbb{F}_p^n,S \cup S^{-1})$? And also in reverse that is take any generating set that gives me a Cayley graph and get a basis out of it? – user6818 Apr 09 '15 at 19:58
  • Correct (AFAICT). – Jyrki Lahtonen Apr 09 '15 at 19:59
  • 1
    AFAICT = As Far As I Can Think ? :D – user6818 Apr 09 '15 at 20:00
  • Though its not very clear to me as to given a symmetric generating set $S$ of the group $\mathbb{F}_{p}^n$ how I can convert this into a (size $n$) basis of $\mathbb{F}_p^n$ over $\mathbb{F}_p$... (though there one is guaranteed that $Cay(\mathbb{F}_p^n,S )$ is connected - right?) – user6818 Apr 09 '15 at 20:02
  • Also, if I take any set of $m$ vectors (say $S$) in $\mathbb{F}_p^d$ and construct the Cayley graph over the Abelian group (under addition modulo $p$) $\mathbb{F}_p^d$ with the generating set $S \cup S^{-1}$ then is this regular Cayley graph guaranteed to be connected? What properties are required of these $m$ vectors to assure that? – user6818 Apr 09 '15 at 20:10

1 Answers1

2

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

Chris Godsil
  • 13,703
  • (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 09 '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 09 '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 09 '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 09 '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 09 '15 at 19:36
  • I guess you mean that we can look at the $n-$sums of eigenvalues of $C_p$ to get the eigenvalues of this disconnected Cayley graph. But are those eigenvalues or just even the spectral gap seen by some property of $M$? – user6818 Apr 09 '15 at 19:39
  • @user6818: It's not at all clear what you mean by the spectrum of a matrix over a finite field. – Chris Godsil Apr 09 '15 at 19:40
  • (1) Isn't there something we can do to the generating set $S \cup S^{-1}$ without changing the Cayley graph which will let us assume that them being stacked as columns of $M$ always give it to be a symmetric matrix - and hence be assured of its spectrum being defined over reals? (2) Is there a natural choice of a generating set for getting a connected Cayley graph over the Abelian group $\mathbb{F}_{p^k}^n$? – user6818 Apr 09 '15 at 19:55