Reputation
265
Top tag
Next privilege 500 Rep.
Access review queues
Badges
2 12
Impact
~6k people reached

11h
comment What is known about optimization of spectral properties of matrices over finite fields?
And how do you know that this is error free? Since we cannot find the roots of a polynomial exactly in anyway how is this exact?
1d
comment What is known about optimization of spectral properties of matrices over finite fields?
Can you kindly link to any reference about how this is possible?
2d
comment What is known about optimization of spectral properties of matrices over finite fields?
no matter how good an approximation one gets its never going to be sufficient to answer various possible questions about spectral gaps - like say deciding if a graph is ramanujan or not.
2d
comment What is known about optimization of spectral properties of matrices over finite fields?
What else would be the way to express the spectral gap of a given matrix?
2d
comment What is known about optimization of spectral properties of matrices over finite fields?
Just wanted to emphasize that the entries are restricted to come from some specific integers.
2d
asked What is known about optimization of spectral properties of matrices over finite fields?
Apr
14
asked What is a good free software to draw complicated Venn diagrams?
Apr
10
comment About Cayley graphs on finite fields
Yeah - but I thought the connectivity of the idea would be lost if I split it up - the three issues looked very closely knit together and hence splitting that up didn't make sense to me - one would have to anyway refer between them to explain the question - but I can also see yoru point! (do feel free to post an "answer"!)
Apr
10
comment About Cayley graphs on finite fields
(1) I guess you mean $S \cup S^{-1}$ in the above. (2) So in the reduction constriction I stated above I guess it follows that the Cayley graph thus obtained is guaranteed to be connected only if one is using $d$ linearly independent columns (which are vectors in $\mathbb{F}_2^d$) to construct a Cayley graph over $\mathbb{F}_2^d$
Apr
10
comment About Cayley graphs on finite fields
(column rank has to be equal to the row rank and hence there must exist $k$ linearly independent columns) How does one here know that this Cayley graph would be connected?
Apr
10
comment About Cayley graphs on finite fields
[This worries when when people do a NP-hardness reduction from the minimum weight codeword problem to lower bounding the spectral gap of a graph. One says that a code is a choice of subspace of the form $\{0,1\}^k$ inside $ \{ 0,1 \}^n$. So one can take a size $k$ basis of this k-dimensional subspace and stack them as rows of a $k \times n$ matrix and then generate a k-regular Cayley graph on $\mathbb{F}_2^n = \{ 0,1\}^n$ using the columns of this matrix as generators.
Apr
10
comment About Cayley graphs on finite fields
Didn't get you! You want the vectors in $S \cup S^{-1}$ to form a basis of $\mathbb{F}_p^d$ as a $d$ dimensional vector space over $\mathbb{F}_p$ for the corresponding Cayley graph to be connected?
Apr
10
comment About Cayley graphs on finite fields
Thanks! And as to the second part of my (1), do the vectors in $S \cup S^{-1}$ have a linear algebraic condition (as vectors in $\mathbb{F}_p^d$) being satisfied when the Cayley graph generated by them is connected?
Apr
10
comment About Cayley graphs on finite fields
Thanks! I am unable to see a clear proof of the (1)?
Apr
10
asked About Cayley graphs on finite fields
Apr
9
comment About Cayley graphs on finite fields.
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?
Apr
9
comment About Cayley graphs on finite fields.
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?)
Apr
9
comment About Cayley graphs on finite fields.
AFAICT = As Far As I Can Think ? :D
Apr
9
comment About Cayley graphs on finite fields.
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?
Apr
9
comment About Cayley graphs on finite fields.
(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$?