Regular graphs has exactly one main eigenvalue
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
An eigenvalue $lambda_1 $ is said to be a main eigenvalue if it has an associated eigenvector $x_1 $ whose sum of entries is nonzero, in other words the projection of $e $, the all ones vector, onto the eigenspace $W_lambda_1$ corresponding to $lambda_1 $ should be nonzero.
A graph $G $ is $k $-regular if each of its vertices is of degree $k $.
It is known that a graph $G$ on $n$ vertices is said to be $k$-regular graph if and only if its corresponding adjacency matrix has exactly one main eigenvalue.
Now I'm trying to prove the sufficient condition, i.e. a graph $G $ with one main eigenvalue is $k $-regular.
I notice that the projection of $e $ onto the rest of the eigenspaces other than $W_lambda_1 $ is zero (since there exists only one maineigenvalue).
Moreover, $e$ can be written as a linear combination of the basis of the eigenspaces corresponding to the $lambda_1,lambda_2,...,lambda_n $ eigenvalues of $G $, hence, $e= proj_W_1=span (x_1)(e)x_1= c x_1$ with c a nonzero constant.
So $G $ is regular.
Is my proof true? Thank you
My explicit proof:
Let $lambda_1^(m_1), lambda_2^(m_2),..., lambda_s^(m_s)$ be the spectrum of $G$ counting multiplicities, and for $j=1, 2,..., s$, let $w_j1,w_j2,...,w_jm_j $ be the eigenvectors corersponding to $lambda_j$ hence the eigenspace corresponding to each eigenvalue $lambda_j$ is $W_j= span(w_j1,..., w_jm_j)$ i.e. $(w_j1,..., w_jm_j)$ makes up the basis of $W_j$. We consider $lambda_1$ to be the only main eigenvalue of $G$ (so $m_1=1$) and $w_11$ is its only corresponding eigenvector whose sum of entries is nonzero.
Thus by Lemma 1.4.1, $proj_W_1=span(w_11)(textbfe)= (w_11, textbfe)w_11 ne 0$. We deduce for $j=2,...,s,$ $ proj_W_j(textbfe)= 0$.
Now, textbfe can be written as a linear combination of basis of the eigenspaces $W_j$ for $j=1,...,s$, thus $textbfe= sum_j=1^ssum_k=1^m_j(w_jk, textbfe)w_jk=underbrace(w_11, textbfe)_= c ne 0 w_11+
sum_j=2^sunderbraceproj_W_j(textbfe)_0= cw_11$
Therefore, $A(G)textbfe= A(G)cw_11= cA(G)w_11= clambda_1w_11= lambda_1cw_11= lambda_1 textbfe$.
spectral-graph-theory adjacency-matrix
asked Aug 15 at 10:36
sal.f
11410
add a comment |Â
up vote
0
down vote
favorite
An eigenvalue $lambda_1 $ is said to be a main eigenvalue if it has an associated eigenvector $x_1 $ whose sum of entries is nonzero, in other words the projection of $e $, the all ones vector, onto the eigenspace $W_lambda_1$ corresponding to $lambda_1 $ should be nonzero.
A graph $G $ is $k $-regular if each of its vertices is of degree $k $.
It is known that a graph $G$ on $n$ vertices is said to be $k$-regular graph if and only if its corresponding adjacency matrix has exactly one main eigenvalue.
Now I'm trying to prove the sufficient condition, i.e. a graph $G $ with one main eigenvalue is $k $-regular.
I notice that the projection of $e $ onto the rest of the eigenspaces other than $W_lambda_1 $ is zero (since there exists only one maineigenvalue).
Moreover, $e$ can be written as a linear combination of the basis of the eigenspaces corresponding to the $lambda_1,lambda_2,...,lambda_n $ eigenvalues of $G $, hence, $e= proj_W_1=span (x_1)(e)x_1= c x_1$ with c a nonzero constant.
So $G $ is regular.
Is my proof true? Thank you
My explicit proof:
Let $lambda_1^(m_1), lambda_2^(m_2),..., lambda_s^(m_s)$ be the spectrum of $G$ counting multiplicities, and for $j=1, 2,..., s$, let $w_j1,w_j2,...,w_jm_j $ be the eigenvectors corersponding to $lambda_j$ hence the eigenspace corresponding to each eigenvalue $lambda_j$ is $W_j= span(w_j1,..., w_jm_j)$ i.e. $(w_j1,..., w_jm_j)$ makes up the basis of $W_j$. We consider $lambda_1$ to be the only main eigenvalue of $G$ (so $m_1=1$) and $w_11$ is its only corresponding eigenvector whose sum of entries is nonzero.
Thus by Lemma 1.4.1, $proj_W_1=span(w_11)(textbfe)= (w_11, textbfe)w_11 ne 0$. We deduce for $j=2,...,s,$ $ proj_W_j(textbfe)= 0$.
Now, textbfe can be written as a linear combination of basis of the eigenspaces $W_j$ for $j=1,...,s$, thus $textbfe= sum_j=1^ssum_k=1^m_j(w_jk, textbfe)w_jk=underbrace(w_11, textbfe)_= c ne 0 w_11+
sum_j=2^sunderbraceproj_W_j(textbfe)_0= cw_11$
Therefore, $A(G)textbfe= A(G)cw_11= cA(G)w_11= clambda_1w_11= lambda_1cw_11= lambda_1 textbfe$.
spectral-graph-theory adjacency-matrix
asked Aug 15 at 10:36
sal.f
11410
You appear to be assuming $G$ is connected; this is reasonable but should be explicit.
– Chris Godsil
Aug 15 at 12:26
Yes, G is connected. I wrote the proof explicitly, just added it in the body. But I have a problem. I reached that $A(G)textbfe= lambda_1textbfe$ but I cannot deduce that $G$ is $lambda_1$ regular unless I know that $lambda_1$ is an integer. Can I know? or is this may not be the correct approach?
– sal.f
Aug 16 at 10:49
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
An eigenvalue $lambda_1 $ is said to be a main eigenvalue if it has an associated eigenvector $x_1 $ whose sum of entries is nonzero, in other words the projection of $e $, the all ones vector, onto the eigenspace $W_lambda_1$ corresponding to $lambda_1 $ should be nonzero.
A graph $G $ is $k $-regular if each of its vertices is of degree $k $.
It is known that a graph $G$ on $n$ vertices is said to be $k$-regular graph if and only if its corresponding adjacency matrix has exactly one main eigenvalue.
Now I'm trying to prove the sufficient condition, i.e. a graph $G $ with one main eigenvalue is $k $-regular.
I notice that the projection of $e $ onto the rest of the eigenspaces other than $W_lambda_1 $ is zero (since there exists only one maineigenvalue).
Moreover, $e$ can be written as a linear combination of the basis of the eigenspaces corresponding to the $lambda_1,lambda_2,...,lambda_n $ eigenvalues of $G $, hence, $e= proj_W_1=span (x_1)(e)x_1= c x_1$ with c a nonzero constant.
So $G $ is regular.
Is my proof true? Thank you
My explicit proof:
Let $lambda_1^(m_1), lambda_2^(m_2),..., lambda_s^(m_s)$ be the spectrum of $G$ counting multiplicities, and for $j=1, 2,..., s$, let $w_j1,w_j2,...,w_jm_j $ be the eigenvectors corersponding to $lambda_j$ hence the eigenspace corresponding to each eigenvalue $lambda_j$ is $W_j= span(w_j1,..., w_jm_j)$ i.e. $(w_j1,..., w_jm_j)$ makes up the basis of $W_j$. We consider $lambda_1$ to be the only main eigenvalue of $G$ (so $m_1=1$) and $w_11$ is its only corresponding eigenvector whose sum of entries is nonzero.
Thus by Lemma 1.4.1, $proj_W_1=span(w_11)(textbfe)= (w_11, textbfe)w_11 ne 0$. We deduce for $j=2,...,s,$ $ proj_W_j(textbfe)= 0$.
Now, textbfe can be written as a linear combination of basis of the eigenspaces $W_j$ for $j=1,...,s$, thus $textbfe= sum_j=1^ssum_k=1^m_j(w_jk, textbfe)w_jk=underbrace(w_11, textbfe)_= c ne 0 w_11+
sum_j=2^sunderbraceproj_W_j(textbfe)_0= cw_11$
Therefore, $A(G)textbfe= A(G)cw_11= cA(G)w_11= clambda_1w_11= lambda_1cw_11= lambda_1 textbfe$.
spectral-graph-theory adjacency-matrix
asked Aug 15 at 10:36
sal.f
11410
An eigenvalue $lambda_1 $ is said to be a main eigenvalue if it has an associated eigenvector $x_1 $ whose sum of entries is nonzero, in other words the projection of $e $, the all ones vector, onto the eigenspace $W_lambda_1$ corresponding to $lambda_1 $ should be nonzero.
A graph $G $ is $k $-regular if each of its vertices is of degree $k $.
It is known that a graph $G$ on $n$ vertices is said to be $k$-regular graph if and only if its corresponding adjacency matrix has exactly one main eigenvalue.
Now I'm trying to prove the sufficient condition, i.e. a graph $G $ with one main eigenvalue is $k $-regular.
I notice that the projection of $e $ onto the rest of the eigenspaces other than $W_lambda_1 $ is zero (since there exists only one maineigenvalue).
Moreover, $e$ can be written as a linear combination of the basis of the eigenspaces corresponding to the $lambda_1,lambda_2,...,lambda_n $ eigenvalues of $G $, hence, $e= proj_W_1=span (x_1)(e)x_1= c x_1$ with c a nonzero constant.
So $G $ is regular.
Is my proof true? Thank you
My explicit proof:
Let $lambda_1^(m_1), lambda_2^(m_2),..., lambda_s^(m_s)$ be the spectrum of $G$ counting multiplicities, and for $j=1, 2,..., s$, let $w_j1,w_j2,...,w_jm_j $ be the eigenvectors corersponding to $lambda_j$ hence the eigenspace corresponding to each eigenvalue $lambda_j$ is $W_j= span(w_j1,..., w_jm_j)$ i.e. $(w_j1,..., w_jm_j)$ makes up the basis of $W_j$. We consider $lambda_1$ to be the only main eigenvalue of $G$ (so $m_1=1$) and $w_11$ is its only corresponding eigenvector whose sum of entries is nonzero.
Thus by Lemma 1.4.1, $proj_W_1=span(w_11)(textbfe)= (w_11, textbfe)w_11 ne 0$. We deduce for $j=2,...,s,$ $ proj_W_j(textbfe)= 0$.
Now, textbfe can be written as a linear combination of basis of the eigenspaces $W_j$ for $j=1,...,s$, thus $textbfe= sum_j=1^ssum_k=1^m_j(w_jk, textbfe)w_jk=underbrace(w_11, textbfe)_= c ne 0 w_11+
sum_j=2^sunderbraceproj_W_j(textbfe)_0= cw_11$
Therefore, $A(G)textbfe= A(G)cw_11= cA(G)w_11= clambda_1w_11= lambda_1cw_11= lambda_1 textbfe$.
spectral-graph-theory adjacency-matrix
asked Aug 15 at 10:36
sal.f
11410
edited Aug 16 at 10:24
asked Aug 15 at 10:36
sal.f
11410
asked Aug 15 at 10:36
sal.f
11410
asked Aug 15 at 10:36
sal.f
11410
11410
You appear to be assuming $G$ is connected; this is reasonable but should be explicit.
– Chris Godsil
Aug 15 at 12:26
Yes, G is connected. I wrote the proof explicitly, just added it in the body. But I have a problem. I reached that $A(G)textbfe= lambda_1textbfe$ but I cannot deduce that $G$ is $lambda_1$ regular unless I know that $lambda_1$ is an integer. Can I know? or is this may not be the correct approach?
– sal.f
Aug 16 at 10:49
add a comment |Â
You appear to be assuming $G$ is connected; this is reasonable but should be explicit.
– Chris Godsil
Aug 15 at 12:26
Yes, G is connected. I wrote the proof explicitly, just added it in the body. But I have a problem. I reached that $A(G)textbfe= lambda_1textbfe$ but I cannot deduce that $G$ is $lambda_1$ regular unless I know that $lambda_1$ is an integer. Can I know? or is this may not be the correct approach?
– sal.f
Aug 16 at 10:49
You appear to be assuming $G$ is connected; this is reasonable but should be explicit.
– Chris Godsil
Aug 15 at 12:26
You appear to be assuming $G$ is connected; this is reasonable but should be explicit.
– Chris Godsil
Aug 15 at 12:26
Yes, G is connected. I wrote the proof explicitly, just added it in the body. But I have a problem. I reached that $A(G)textbfe= lambda_1textbfe$ but I cannot deduce that $G$ is $lambda_1$ regular unless I know that $lambda_1$ is an integer. Can I know? or is this may not be the correct approach?
– sal.f
Aug 16 at 10:49
Yes, G is connected. I wrote the proof explicitly, just added it in the body. But I have a problem. I reached that $A(G)textbfe= lambda_1textbfe$ but I cannot deduce that $G$ is $lambda_1$ regular unless I know that $lambda_1$ is an integer. Can I know? or is this may not be the correct approach?
– sal.f
Aug 16 at 10:49
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2883456%2fregular-graphs-has-exactly-one-main-eigenvalue%23new-answer', 'question_page');
);
Post as a guest
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
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
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
You appear to be assuming $G$ is connected; this is reasonable but should be explicit.
– Chris Godsil
Aug 15 at 12:26
Yes, G is connected. I wrote the proof explicitly, just added it in the body. But I have a problem. I reached that $A(G)textbfe= lambda_1textbfe$ but I cannot deduce that $G$ is $lambda_1$ regular unless I know that $lambda_1$ is an integer. Can I know? or is this may not be the correct approach?
– sal.f
Aug 16 at 10:49