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?










share|cite|improve this question


























    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?










    share|cite|improve this question
























      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?










      share|cite|improve this question













      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






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked Nov 13 at 1:40









      Dan P.

      697




      697






















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






          share|cite|improve this answer





















            Your Answer





            StackExchange.ifUsing("editor", function () {
            return StackExchange.using("mathjaxEditing", function () {
            StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
            StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
            });
            });
            }, "mathjax-editing");

            StackExchange.ready(function() {
            var channelOptions = {
            tags: "".split(" "),
            id: "69"
            };
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function() {
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled) {
            StackExchange.using("snippets", function() {
            createEditor();
            });
            }
            else {
            createEditor();
            }
            });

            function createEditor() {
            StackExchange.prepareEditor({
            heartbeatType: 'answer',
            convertImagesToLinks: true,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: 10,
            bindNavPrevention: true,
            postfix: "",
            imageUploader: {
            brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
            contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
            allowUrls: true
            },
            noCode: true, onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            });


            }
            });














            draft saved

            draft discarded


















            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

























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






            share|cite|improve this answer

























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






              share|cite|improve this answer























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






                share|cite|improve this answer












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







                share|cite|improve this answer












                share|cite|improve this answer



                share|cite|improve this answer










                answered Nov 18 at 2:44









                Dan P.

                697




                697






























                    draft saved

                    draft discarded




















































                    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.




                    draft saved


                    draft discarded














                    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





















































                    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







                    Popular posts from this blog

                    QoS: MAC-Priority for clients behind a repeater

                    Ивакино (Тотемский район)

                    Can't locate Autom4te/ChannelDefs.pm in @INC (when it definitely is there)