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