Connected digraph, the rank $M=V-1$
Clash 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
linear-algebra graph-theory matrix-rank directed-graphs
add a comment |Â
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
linear-algebra graph-theory matrix-rank directed-graphs
add a comment |Â
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
linear-algebra graph-theory matrix-rank directed-graphs
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
linear-algebra graph-theory matrix-rank directed-graphs
asked Sep 9 at 8:53
Jason Ng
537
537
add a comment |Â
add a comment |Â
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.
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
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.
add a comment |Â
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.
add a comment |Â
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.
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.
answered Sep 9 at 18:30
Misha Lavrov
38.3k55094
38.3k55094
add a comment |Â
add a comment |Â
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%2f2910562%2fconnected-digraph-the-rank-m-v-1%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