Prove that a strongly regular graph is imprimitive $iff$ $0$ or $-1$ is an eigenvalue.
up vote
1
down vote
favorite
First, let $X$ be a strongly regular graph (SRG) with parameters $(n,k,a,c)$ and let $A$ be the adjacency matrix of $X$. Primitive implies that $0<c<k$. We know that $A$ has only 3 eigenvalues, which are of the form:
$$k, qquad theta=dfrac{(a-c)+ sqrt{(a-c)^2+4(k-c)}}{2}, qquad tau =dfrac{(a-c)- sqrt{(a-c)^2+4(k-c)}}{2}.$$
So if $0$ is an eigenvalue of $A$, then we can plug this into the formulas above:
$$0= dfrac{(a-c)pm sqrt{(a-c)^2+4(k-c)}}{2} implies c=k,$$
and so we have $0<cnot<k$, which implies that $X$ is imprimitive. Similarly, if $-1$ is an eigenvalue of $A$, then we have
$$-1=dfrac{(a-c)pm sqrt{(a-c)^2+4(k-c)}}{2} implies a=k-1.$$
Question 1: I know that since $X$ is a SRG with parameters $(n,k,a,c)$, then $overline{X}$ is a SRG with parameters $(n,n-k-1,n-2-2k+c,n-2k+a)$. So if a substitute $a=k-1$ into the last parameter of $overline{X}$, I get $n-k-1$. Can I say that since $0<c<k$ for $X$ implies primitive, then $0<n-k-1not<n-k-1$ implies that $X$ must be imprimitive?
Question 2: I don't know how to show the converse. That is, if I suppose that $X$ is imprimitive, how do I show that $0$ or $-1$ must be an eigenvalue?
linear-algebra graph-theory eigenvalues-eigenvectors
add a comment |
up vote
1
down vote
favorite
First, let $X$ be a strongly regular graph (SRG) with parameters $(n,k,a,c)$ and let $A$ be the adjacency matrix of $X$. Primitive implies that $0<c<k$. We know that $A$ has only 3 eigenvalues, which are of the form:
$$k, qquad theta=dfrac{(a-c)+ sqrt{(a-c)^2+4(k-c)}}{2}, qquad tau =dfrac{(a-c)- sqrt{(a-c)^2+4(k-c)}}{2}.$$
So if $0$ is an eigenvalue of $A$, then we can plug this into the formulas above:
$$0= dfrac{(a-c)pm sqrt{(a-c)^2+4(k-c)}}{2} implies c=k,$$
and so we have $0<cnot<k$, which implies that $X$ is imprimitive. Similarly, if $-1$ is an eigenvalue of $A$, then we have
$$-1=dfrac{(a-c)pm sqrt{(a-c)^2+4(k-c)}}{2} implies a=k-1.$$
Question 1: I know that since $X$ is a SRG with parameters $(n,k,a,c)$, then $overline{X}$ is a SRG with parameters $(n,n-k-1,n-2-2k+c,n-2k+a)$. So if a substitute $a=k-1$ into the last parameter of $overline{X}$, I get $n-k-1$. Can I say that since $0<c<k$ for $X$ implies primitive, then $0<n-k-1not<n-k-1$ implies that $X$ must be imprimitive?
Question 2: I don't know how to show the converse. That is, if I suppose that $X$ is imprimitive, how do I show that $0$ or $-1$ must be an eigenvalue?
linear-algebra graph-theory eigenvalues-eigenvectors
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
First, let $X$ be a strongly regular graph (SRG) with parameters $(n,k,a,c)$ and let $A$ be the adjacency matrix of $X$. Primitive implies that $0<c<k$. We know that $A$ has only 3 eigenvalues, which are of the form:
$$k, qquad theta=dfrac{(a-c)+ sqrt{(a-c)^2+4(k-c)}}{2}, qquad tau =dfrac{(a-c)- sqrt{(a-c)^2+4(k-c)}}{2}.$$
So if $0$ is an eigenvalue of $A$, then we can plug this into the formulas above:
$$0= dfrac{(a-c)pm sqrt{(a-c)^2+4(k-c)}}{2} implies c=k,$$
and so we have $0<cnot<k$, which implies that $X$ is imprimitive. Similarly, if $-1$ is an eigenvalue of $A$, then we have
$$-1=dfrac{(a-c)pm sqrt{(a-c)^2+4(k-c)}}{2} implies a=k-1.$$
Question 1: I know that since $X$ is a SRG with parameters $(n,k,a,c)$, then $overline{X}$ is a SRG with parameters $(n,n-k-1,n-2-2k+c,n-2k+a)$. So if a substitute $a=k-1$ into the last parameter of $overline{X}$, I get $n-k-1$. Can I say that since $0<c<k$ for $X$ implies primitive, then $0<n-k-1not<n-k-1$ implies that $X$ must be imprimitive?
Question 2: I don't know how to show the converse. That is, if I suppose that $X$ is imprimitive, how do I show that $0$ or $-1$ must be an eigenvalue?
linear-algebra graph-theory eigenvalues-eigenvectors
First, let $X$ be a strongly regular graph (SRG) with parameters $(n,k,a,c)$ and let $A$ be the adjacency matrix of $X$. Primitive implies that $0<c<k$. We know that $A$ has only 3 eigenvalues, which are of the form:
$$k, qquad theta=dfrac{(a-c)+ sqrt{(a-c)^2+4(k-c)}}{2}, qquad tau =dfrac{(a-c)- sqrt{(a-c)^2+4(k-c)}}{2}.$$
So if $0$ is an eigenvalue of $A$, then we can plug this into the formulas above:
$$0= dfrac{(a-c)pm sqrt{(a-c)^2+4(k-c)}}{2} implies c=k,$$
and so we have $0<cnot<k$, which implies that $X$ is imprimitive. Similarly, if $-1$ is an eigenvalue of $A$, then we have
$$-1=dfrac{(a-c)pm sqrt{(a-c)^2+4(k-c)}}{2} implies a=k-1.$$
Question 1: I know that since $X$ is a SRG with parameters $(n,k,a,c)$, then $overline{X}$ is a SRG with parameters $(n,n-k-1,n-2-2k+c,n-2k+a)$. So if a substitute $a=k-1$ into the last parameter of $overline{X}$, I get $n-k-1$. Can I say that since $0<c<k$ for $X$ implies primitive, then $0<n-k-1not<n-k-1$ implies that $X$ must be imprimitive?
Question 2: I don't know how to show the converse. That is, if I suppose that $X$ is imprimitive, how do I show that $0$ or $-1$ must be an eigenvalue?
linear-algebra graph-theory eigenvalues-eigenvectors
linear-algebra graph-theory eigenvalues-eigenvectors
asked Nov 13 at 1:40
Dan P.
697
697
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
I think I've solved the question. In case someone else is interested in this question, I've included my solution below:
Let $X$ be a strongly regular graph (SRG) with parameters $(n,k,a,c)$ and let $A$ be the adjacency matrix of $X$. Primitive implies that $0<c<k$. We know that $A$ has only 3 eigenvalues, which are of the form:
$$k, qquad theta=dfrac{(a-c)+ sqrt{(a-c)^2+4(k-c)}}{2}, qquad tau =dfrac{(a-c)- sqrt{(a-c)^2+4(k-c)}}{2}.$$
So if $0$ is an eigenvalue of $A$, then we can plug this into the formulas above:
$$0= dfrac{(a-c)pm sqrt{(a-c)^2+4(k-c)}}{2} implies c=k,$$
and so we have $0<cnot<k$; therefore, $X$ is imprimitive. Similarly, if $-1$ is an eigenvalue of $A$, then we have
$$-1=dfrac{(a-c)pm sqrt{(a-c)^2+4(k-c)}}{2} implies a=k-1.$$
So then for $overline{X}$ we have $0<n-k-1 not< n-k-1$, and so $X$ is imprimitive.
Conversely, suppose that $X$ is imprimitive. Then either $X$ or $overline{X}$ is disconnected. If $X$ is disconnected, then $c=0$ for $X$, which implies that within any connected component of $X$, no two pair of non-adjacent vertices have a common neighbour. Hence, $X=cup K_n$. Let $A(K_n)$ be the adjacency matrix for $K_n$. Then $A(K_n)=J-I$, where $J$ is the all-ones matrix and $I$ is the identity matrix. Since $J$ has spectrum $n$ and $0^{n-1}$ and $I$ has spectrum $1^n$ (and $IJ=JI$), it follows that $K_n$ has spectrum $(n-1)^1$ and $(-1)^{n-1}$ and so $-1$ is an eigenvalue of $X$. Similarly, if $overline{X}$ is disconnected, then it follows that $X=cupoverline{K}_n$, where the spectrum of $A(overline{K}_n)=J-I-A(K_n)$ is $0^n$; hence, $0$ is an eigenvalue of $X$.
Therefore, if $X$ is imprimitive, then $-1$ or $0$ is an eigenvalue of $X$.
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
I think I've solved the question. In case someone else is interested in this question, I've included my solution below:
Let $X$ be a strongly regular graph (SRG) with parameters $(n,k,a,c)$ and let $A$ be the adjacency matrix of $X$. Primitive implies that $0<c<k$. We know that $A$ has only 3 eigenvalues, which are of the form:
$$k, qquad theta=dfrac{(a-c)+ sqrt{(a-c)^2+4(k-c)}}{2}, qquad tau =dfrac{(a-c)- sqrt{(a-c)^2+4(k-c)}}{2}.$$
So if $0$ is an eigenvalue of $A$, then we can plug this into the formulas above:
$$0= dfrac{(a-c)pm sqrt{(a-c)^2+4(k-c)}}{2} implies c=k,$$
and so we have $0<cnot<k$; therefore, $X$ is imprimitive. Similarly, if $-1$ is an eigenvalue of $A$, then we have
$$-1=dfrac{(a-c)pm sqrt{(a-c)^2+4(k-c)}}{2} implies a=k-1.$$
So then for $overline{X}$ we have $0<n-k-1 not< n-k-1$, and so $X$ is imprimitive.
Conversely, suppose that $X$ is imprimitive. Then either $X$ or $overline{X}$ is disconnected. If $X$ is disconnected, then $c=0$ for $X$, which implies that within any connected component of $X$, no two pair of non-adjacent vertices have a common neighbour. Hence, $X=cup K_n$. Let $A(K_n)$ be the adjacency matrix for $K_n$. Then $A(K_n)=J-I$, where $J$ is the all-ones matrix and $I$ is the identity matrix. Since $J$ has spectrum $n$ and $0^{n-1}$ and $I$ has spectrum $1^n$ (and $IJ=JI$), it follows that $K_n$ has spectrum $(n-1)^1$ and $(-1)^{n-1}$ and so $-1$ is an eigenvalue of $X$. Similarly, if $overline{X}$ is disconnected, then it follows that $X=cupoverline{K}_n$, where the spectrum of $A(overline{K}_n)=J-I-A(K_n)$ is $0^n$; hence, $0$ is an eigenvalue of $X$.
Therefore, if $X$ is imprimitive, then $-1$ or $0$ is an eigenvalue of $X$.
add a comment |
up vote
0
down vote
accepted
I think I've solved the question. In case someone else is interested in this question, I've included my solution below:
Let $X$ be a strongly regular graph (SRG) with parameters $(n,k,a,c)$ and let $A$ be the adjacency matrix of $X$. Primitive implies that $0<c<k$. We know that $A$ has only 3 eigenvalues, which are of the form:
$$k, qquad theta=dfrac{(a-c)+ sqrt{(a-c)^2+4(k-c)}}{2}, qquad tau =dfrac{(a-c)- sqrt{(a-c)^2+4(k-c)}}{2}.$$
So if $0$ is an eigenvalue of $A$, then we can plug this into the formulas above:
$$0= dfrac{(a-c)pm sqrt{(a-c)^2+4(k-c)}}{2} implies c=k,$$
and so we have $0<cnot<k$; therefore, $X$ is imprimitive. Similarly, if $-1$ is an eigenvalue of $A$, then we have
$$-1=dfrac{(a-c)pm sqrt{(a-c)^2+4(k-c)}}{2} implies a=k-1.$$
So then for $overline{X}$ we have $0<n-k-1 not< n-k-1$, and so $X$ is imprimitive.
Conversely, suppose that $X$ is imprimitive. Then either $X$ or $overline{X}$ is disconnected. If $X$ is disconnected, then $c=0$ for $X$, which implies that within any connected component of $X$, no two pair of non-adjacent vertices have a common neighbour. Hence, $X=cup K_n$. Let $A(K_n)$ be the adjacency matrix for $K_n$. Then $A(K_n)=J-I$, where $J$ is the all-ones matrix and $I$ is the identity matrix. Since $J$ has spectrum $n$ and $0^{n-1}$ and $I$ has spectrum $1^n$ (and $IJ=JI$), it follows that $K_n$ has spectrum $(n-1)^1$ and $(-1)^{n-1}$ and so $-1$ is an eigenvalue of $X$. Similarly, if $overline{X}$ is disconnected, then it follows that $X=cupoverline{K}_n$, where the spectrum of $A(overline{K}_n)=J-I-A(K_n)$ is $0^n$; hence, $0$ is an eigenvalue of $X$.
Therefore, if $X$ is imprimitive, then $-1$ or $0$ is an eigenvalue of $X$.
add a comment |
up vote
0
down vote
accepted
up vote
0
down vote
accepted
I think I've solved the question. In case someone else is interested in this question, I've included my solution below:
Let $X$ be a strongly regular graph (SRG) with parameters $(n,k,a,c)$ and let $A$ be the adjacency matrix of $X$. Primitive implies that $0<c<k$. We know that $A$ has only 3 eigenvalues, which are of the form:
$$k, qquad theta=dfrac{(a-c)+ sqrt{(a-c)^2+4(k-c)}}{2}, qquad tau =dfrac{(a-c)- sqrt{(a-c)^2+4(k-c)}}{2}.$$
So if $0$ is an eigenvalue of $A$, then we can plug this into the formulas above:
$$0= dfrac{(a-c)pm sqrt{(a-c)^2+4(k-c)}}{2} implies c=k,$$
and so we have $0<cnot<k$; therefore, $X$ is imprimitive. Similarly, if $-1$ is an eigenvalue of $A$, then we have
$$-1=dfrac{(a-c)pm sqrt{(a-c)^2+4(k-c)}}{2} implies a=k-1.$$
So then for $overline{X}$ we have $0<n-k-1 not< n-k-1$, and so $X$ is imprimitive.
Conversely, suppose that $X$ is imprimitive. Then either $X$ or $overline{X}$ is disconnected. If $X$ is disconnected, then $c=0$ for $X$, which implies that within any connected component of $X$, no two pair of non-adjacent vertices have a common neighbour. Hence, $X=cup K_n$. Let $A(K_n)$ be the adjacency matrix for $K_n$. Then $A(K_n)=J-I$, where $J$ is the all-ones matrix and $I$ is the identity matrix. Since $J$ has spectrum $n$ and $0^{n-1}$ and $I$ has spectrum $1^n$ (and $IJ=JI$), it follows that $K_n$ has spectrum $(n-1)^1$ and $(-1)^{n-1}$ and so $-1$ is an eigenvalue of $X$. Similarly, if $overline{X}$ is disconnected, then it follows that $X=cupoverline{K}_n$, where the spectrum of $A(overline{K}_n)=J-I-A(K_n)$ is $0^n$; hence, $0$ is an eigenvalue of $X$.
Therefore, if $X$ is imprimitive, then $-1$ or $0$ is an eigenvalue of $X$.
I think I've solved the question. In case someone else is interested in this question, I've included my solution below:
Let $X$ be a strongly regular graph (SRG) with parameters $(n,k,a,c)$ and let $A$ be the adjacency matrix of $X$. Primitive implies that $0<c<k$. We know that $A$ has only 3 eigenvalues, which are of the form:
$$k, qquad theta=dfrac{(a-c)+ sqrt{(a-c)^2+4(k-c)}}{2}, qquad tau =dfrac{(a-c)- sqrt{(a-c)^2+4(k-c)}}{2}.$$
So if $0$ is an eigenvalue of $A$, then we can plug this into the formulas above:
$$0= dfrac{(a-c)pm sqrt{(a-c)^2+4(k-c)}}{2} implies c=k,$$
and so we have $0<cnot<k$; therefore, $X$ is imprimitive. Similarly, if $-1$ is an eigenvalue of $A$, then we have
$$-1=dfrac{(a-c)pm sqrt{(a-c)^2+4(k-c)}}{2} implies a=k-1.$$
So then for $overline{X}$ we have $0<n-k-1 not< n-k-1$, and so $X$ is imprimitive.
Conversely, suppose that $X$ is imprimitive. Then either $X$ or $overline{X}$ is disconnected. If $X$ is disconnected, then $c=0$ for $X$, which implies that within any connected component of $X$, no two pair of non-adjacent vertices have a common neighbour. Hence, $X=cup K_n$. Let $A(K_n)$ be the adjacency matrix for $K_n$. Then $A(K_n)=J-I$, where $J$ is the all-ones matrix and $I$ is the identity matrix. Since $J$ has spectrum $n$ and $0^{n-1}$ and $I$ has spectrum $1^n$ (and $IJ=JI$), it follows that $K_n$ has spectrum $(n-1)^1$ and $(-1)^{n-1}$ and so $-1$ is an eigenvalue of $X$. Similarly, if $overline{X}$ is disconnected, then it follows that $X=cupoverline{K}_n$, where the spectrum of $A(overline{K}_n)=J-I-A(K_n)$ is $0^n$; hence, $0$ is an eigenvalue of $X$.
Therefore, if $X$ is imprimitive, then $-1$ or $0$ is an eigenvalue of $X$.
answered Nov 18 at 2:44
Dan P.
697
697
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2996168%2fprove-that-a-strongly-regular-graph-is-imprimitive-iff-0-or-1-is-an-eige%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown