Connected digraph, the rank $M=V-1$

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
1
down vote

favorite












As shown above, how to prove the rank of the incidence matrix is $V-1$?
First, I figure out that the incidence matrix of a digraph will have 1 or -1 (and zero also) in each column (that are edges). Then, from this fact, I prove that the column vectors in $M$ are linearly dependent, so, rank $M < V$ and thus, rank $M leq V-1$.
But suddenly i realize that the digraph is just "connected". It is possible to exist an edge with only connect to one vertex. Then the above proof and logic are wrong. Those are only suitable to use in a digraph iff it contains "cycle". Is it the case?? How can go further to this question










share|cite|improve this question

























    up vote
    1
    down vote

    favorite












    As shown above, how to prove the rank of the incidence matrix is $V-1$?
    First, I figure out that the incidence matrix of a digraph will have 1 or -1 (and zero also) in each column (that are edges). Then, from this fact, I prove that the column vectors in $M$ are linearly dependent, so, rank $M < V$ and thus, rank $M leq V-1$.
    But suddenly i realize that the digraph is just "connected". It is possible to exist an edge with only connect to one vertex. Then the above proof and logic are wrong. Those are only suitable to use in a digraph iff it contains "cycle". Is it the case?? How can go further to this question










    share|cite|improve this question























      up vote
      1
      down vote

      favorite









      up vote
      1
      down vote

      favorite











      As shown above, how to prove the rank of the incidence matrix is $V-1$?
      First, I figure out that the incidence matrix of a digraph will have 1 or -1 (and zero also) in each column (that are edges). Then, from this fact, I prove that the column vectors in $M$ are linearly dependent, so, rank $M < V$ and thus, rank $M leq V-1$.
      But suddenly i realize that the digraph is just "connected". It is possible to exist an edge with only connect to one vertex. Then the above proof and logic are wrong. Those are only suitable to use in a digraph iff it contains "cycle". Is it the case?? How can go further to this question










      share|cite|improve this question













      As shown above, how to prove the rank of the incidence matrix is $V-1$?
      First, I figure out that the incidence matrix of a digraph will have 1 or -1 (and zero also) in each column (that are edges). Then, from this fact, I prove that the column vectors in $M$ are linearly dependent, so, rank $M < V$ and thus, rank $M leq V-1$.
      But suddenly i realize that the digraph is just "connected". It is possible to exist an edge with only connect to one vertex. Then the above proof and logic are wrong. Those are only suitable to use in a digraph iff it contains "cycle". Is it the case?? How can go further to this question







      linear-algebra graph-theory matrix-rank directed-graphs






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked Sep 9 at 8:53









      Jason Ng

      537




      537




















          1 Answer
          1






          active

          oldest

          votes

















          up vote
          0
          down vote



          accepted










          You are right that a linear dependence between columns of the incidence matrices comes from cycles. However, a linear dependence between columns isn't what you're looking for, anyway. The number of columns is $E$, the number of edges; if the columns are linearly dependent, then the rank is less than $E$; however, $E$ may be much larger than $V$, so this doesn't necessarily help.



          Instead, you should be looking for a linear dependence between rows of the incidence matrix. By default, the rank of the matrix is at most $V$, the number of vertices (and therefore the number of rows). If you find a dependence between the rows, then the rank of the matrix is at most $V-1$.



          To start off, you should observe that the sum of the rows of the incidence matrix is $0$. This guarantees that the matrix is has rank at most $V-1$. Then, convince yourself that in a connected graph, this is the only linear dependence between the rows.






          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: false,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: 10,
            bindNavPrevention: true,
            postfix: "",
            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%2f2910562%2fconnected-digraph-the-rank-m-v-1%23new-answer', 'question_page');

            );

            Post as a guest






























            1 Answer
            1






            active

            oldest

            votes








            1 Answer
            1






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes








            up vote
            0
            down vote



            accepted










            You are right that a linear dependence between columns of the incidence matrices comes from cycles. However, a linear dependence between columns isn't what you're looking for, anyway. The number of columns is $E$, the number of edges; if the columns are linearly dependent, then the rank is less than $E$; however, $E$ may be much larger than $V$, so this doesn't necessarily help.



            Instead, you should be looking for a linear dependence between rows of the incidence matrix. By default, the rank of the matrix is at most $V$, the number of vertices (and therefore the number of rows). If you find a dependence between the rows, then the rank of the matrix is at most $V-1$.



            To start off, you should observe that the sum of the rows of the incidence matrix is $0$. This guarantees that the matrix is has rank at most $V-1$. Then, convince yourself that in a connected graph, this is the only linear dependence between the rows.






            share|cite|improve this answer
























              up vote
              0
              down vote



              accepted










              You are right that a linear dependence between columns of the incidence matrices comes from cycles. However, a linear dependence between columns isn't what you're looking for, anyway. The number of columns is $E$, the number of edges; if the columns are linearly dependent, then the rank is less than $E$; however, $E$ may be much larger than $V$, so this doesn't necessarily help.



              Instead, you should be looking for a linear dependence between rows of the incidence matrix. By default, the rank of the matrix is at most $V$, the number of vertices (and therefore the number of rows). If you find a dependence between the rows, then the rank of the matrix is at most $V-1$.



              To start off, you should observe that the sum of the rows of the incidence matrix is $0$. This guarantees that the matrix is has rank at most $V-1$. Then, convince yourself that in a connected graph, this is the only linear dependence between the rows.






              share|cite|improve this answer






















                up vote
                0
                down vote



                accepted







                up vote
                0
                down vote



                accepted






                You are right that a linear dependence between columns of the incidence matrices comes from cycles. However, a linear dependence between columns isn't what you're looking for, anyway. The number of columns is $E$, the number of edges; if the columns are linearly dependent, then the rank is less than $E$; however, $E$ may be much larger than $V$, so this doesn't necessarily help.



                Instead, you should be looking for a linear dependence between rows of the incidence matrix. By default, the rank of the matrix is at most $V$, the number of vertices (and therefore the number of rows). If you find a dependence between the rows, then the rank of the matrix is at most $V-1$.



                To start off, you should observe that the sum of the rows of the incidence matrix is $0$. This guarantees that the matrix is has rank at most $V-1$. Then, convince yourself that in a connected graph, this is the only linear dependence between the rows.






                share|cite|improve this answer












                You are right that a linear dependence between columns of the incidence matrices comes from cycles. However, a linear dependence between columns isn't what you're looking for, anyway. The number of columns is $E$, the number of edges; if the columns are linearly dependent, then the rank is less than $E$; however, $E$ may be much larger than $V$, so this doesn't necessarily help.



                Instead, you should be looking for a linear dependence between rows of the incidence matrix. By default, the rank of the matrix is at most $V$, the number of vertices (and therefore the number of rows). If you find a dependence between the rows, then the rank of the matrix is at most $V-1$.



                To start off, you should observe that the sum of the rows of the incidence matrix is $0$. This guarantees that the matrix is has rank at most $V-1$. Then, convince yourself that in a connected graph, this is the only linear dependence between the rows.







                share|cite|improve this answer












                share|cite|improve this answer



                share|cite|improve this answer










                answered Sep 9 at 18:30









                Misha Lavrov

                38.3k55094




                38.3k55094



























                     

                    draft saved


                    draft discarded















































                     


                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function ()
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2910562%2fconnected-digraph-the-rank-m-v-1%23new-answer', 'question_page');

                    );

                    Post as a guest













































































                    這個網誌中的熱門文章

                    How to combine Bézier curves to a surface?

                    Why am i infinitely getting the same tweet with the Twitter Search API?

                    Carbon dioxide