Show that the incidence matrix of a graph has linear independent columns iff the graph has no cycle [on hold]
up vote
0
down vote
favorite
show that the incidence matrix of a graph has linear independent columns if and only if the graph has no cycles
linear-algebra graph-theory
asked Dec 2 at 5:39
Loulik F
12
New contributor
Loulik F is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
put on hold as unclear what you're asking by Jyrki Lahtonen, user302797, Rebellos, Chinnapparaj R, Paul Frost Dec 2 at 10:27
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
up vote
0
down vote
favorite
show that the incidence matrix of a graph has linear independent columns if and only if the graph has no cycles
linear-algebra graph-theory
asked Dec 2 at 5:39
Loulik F
12
New contributor
Loulik F is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
put on hold as unclear what you're asking by Jyrki Lahtonen, user302797, Rebellos, Chinnapparaj R, Paul Frost Dec 2 at 10:27
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
($Rightarrow$) Let G be a graph on $n$ vertices and let $e_1,dots ,e_k$ be the edges of the incidence matrix of G, denoted $I(G)$. Suppose there is a cycle in the corresponding induced subgraph and WLOG, suppose the edges $e_1,dots ,e_j$ form a cycle. By relabeling the vertices we can see that $begin{bmatrix}B\0end{bmatrix}$ is a submatrix of $I(G)$ formed by the edges $e_1,dots ,e_j$ where $B$ is a $jtimes j$ incidence matrix of the cycle formed by those same edges. Observe that $B$ is a square matrix with columns (edges) that add up to zero.
– Tomás Palamás
Dec 3 at 22:33
Therefore, the edges $e_1,dots ,e_j$ are linearly dependent.
– Tomás Palamás
Dec 3 at 22:33
($Leftarrow$)Now suppose the edges $e_1,dots ,e_k$ induce a graph with no cycle (what is this called?). Hint: Use this, if G is a graph on $n$ vertices and has $l$ components then the rank of $I(G)=n-l$.
– Tomás Palamás
Dec 3 at 22:34
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
show that the incidence matrix of a graph has linear independent columns if and only if the graph has no cycles
linear-algebra graph-theory
asked Dec 2 at 5:39
Loulik F
12
New contributor
Loulik F is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
show that the incidence matrix of a graph has linear independent columns if and only if the graph has no cycles
linear-algebra graph-theory
linear-algebra graph-theory
asked Dec 2 at 5:39
Loulik F
12
New contributor
Loulik F is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Dec 2 at 5:39
Loulik F
12
New contributor
Loulik F is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Dec 2 at 11:43
asked Dec 2 at 5:39
Loulik F
12
New contributor
Loulik F is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Dec 2 at 5:39
Loulik F
12
asked Dec 2 at 5:39
Loulik F
12
12
New contributor
Loulik F is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Loulik F is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Loulik F is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
put on hold as unclear what you're asking by Jyrki Lahtonen, user302797, Rebellos, Chinnapparaj R, Paul Frost Dec 2 at 10:27
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
put on hold as unclear what you're asking by Jyrki Lahtonen, user302797, Rebellos, Chinnapparaj R, Paul Frost Dec 2 at 10:27
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
($Rightarrow$) Let G be a graph on $n$ vertices and let $e_1,dots ,e_k$ be the edges of the incidence matrix of G, denoted $I(G)$. Suppose there is a cycle in the corresponding induced subgraph and WLOG, suppose the edges $e_1,dots ,e_j$ form a cycle. By relabeling the vertices we can see that $begin{bmatrix}B\0end{bmatrix}$ is a submatrix of $I(G)$ formed by the edges $e_1,dots ,e_j$ where $B$ is a $jtimes j$ incidence matrix of the cycle formed by those same edges. Observe that $B$ is a square matrix with columns (edges) that add up to zero.
– Tomás Palamás
Dec 3 at 22:33
Therefore, the edges $e_1,dots ,e_j$ are linearly dependent.
– Tomás Palamás
Dec 3 at 22:33
($Leftarrow$)Now suppose the edges $e_1,dots ,e_k$ induce a graph with no cycle (what is this called?). Hint: Use this, if G is a graph on $n$ vertices and has $l$ components then the rank of $I(G)=n-l$.
– Tomás Palamás
Dec 3 at 22:34
add a comment |
($Rightarrow$) Let G be a graph on $n$ vertices and let $e_1,dots ,e_k$ be the edges of the incidence matrix of G, denoted $I(G)$. Suppose there is a cycle in the corresponding induced subgraph and WLOG, suppose the edges $e_1,dots ,e_j$ form a cycle. By relabeling the vertices we can see that $begin{bmatrix}B\0end{bmatrix}$ is a submatrix of $I(G)$ formed by the edges $e_1,dots ,e_j$ where $B$ is a $jtimes j$ incidence matrix of the cycle formed by those same edges. Observe that $B$ is a square matrix with columns (edges) that add up to zero.
– Tomás Palamás
Dec 3 at 22:33
Therefore, the edges $e_1,dots ,e_j$ are linearly dependent.
– Tomás Palamás
Dec 3 at 22:33
($Leftarrow$)Now suppose the edges $e_1,dots ,e_k$ induce a graph with no cycle (what is this called?). Hint: Use this, if G is a graph on $n$ vertices and has $l$ components then the rank of $I(G)=n-l$.
– Tomás Palamás
Dec 3 at 22:34
($Rightarrow$) Let G be a graph on $n$ vertices and let $e_1,dots ,e_k$ be the edges of the incidence matrix of G, denoted $I(G)$. Suppose there is a cycle in the corresponding induced subgraph and WLOG, suppose the edges $e_1,dots ,e_j$ form a cycle. By relabeling the vertices we can see that $begin{bmatrix}B\0end{bmatrix}$ is a submatrix of $I(G)$ formed by the edges $e_1,dots ,e_j$ where $B$ is a $jtimes j$ incidence matrix of the cycle formed by those same edges. Observe that $B$ is a square matrix with columns (edges) that add up to zero.
– Tomás Palamás
Dec 3 at 22:33
($Rightarrow$) Let G be a graph on $n$ vertices and let $e_1,dots ,e_k$ be the edges of the incidence matrix of G, denoted $I(G)$. Suppose there is a cycle in the corresponding induced subgraph and WLOG, suppose the edges $e_1,dots ,e_j$ form a cycle. By relabeling the vertices we can see that $begin{bmatrix}B\0end{bmatrix}$ is a submatrix of $I(G)$ formed by the edges $e_1,dots ,e_j$ where $B$ is a $jtimes j$ incidence matrix of the cycle formed by those same edges. Observe that $B$ is a square matrix with columns (edges) that add up to zero.
– Tomás Palamás
Dec 3 at 22:33
Therefore, the edges $e_1,dots ,e_j$ are linearly dependent.
– Tomás Palamás
Dec 3 at 22:33
Therefore, the edges $e_1,dots ,e_j$ are linearly dependent.
– Tomás Palamás
Dec 3 at 22:33
($Leftarrow$)Now suppose the edges $e_1,dots ,e_k$ induce a graph with no cycle (what is this called?). Hint: Use this, if G is a graph on $n$ vertices and has $l$ components then the rank of $I(G)=n-l$.
– Tomás Palamás
Dec 3 at 22:34
($Leftarrow$)Now suppose the edges $e_1,dots ,e_k$ induce a graph with no cycle (what is this called?). Hint: Use this, if G is a graph on $n$ vertices and has $l$ components then the rank of $I(G)=n-l$.
– Tomás Palamás
Dec 3 at 22:34
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
($Rightarrow$) Let G be a graph on $n$ vertices and let $e_1,dots ,e_k$ be the edges of the incidence matrix of G, denoted $I(G)$. Suppose there is a cycle in the corresponding induced subgraph and WLOG, suppose the edges $e_1,dots ,e_j$ form a cycle. By relabeling the vertices we can see that $begin{bmatrix}B\0end{bmatrix}$ is a submatrix of $I(G)$ formed by the edges $e_1,dots ,e_j$ where $B$ is a $jtimes j$ incidence matrix of the cycle formed by those same edges. Observe that $B$ is a square matrix with columns (edges) that add up to zero.
– Tomás Palamás
Dec 3 at 22:33
Therefore, the edges $e_1,dots ,e_j$ are linearly dependent.
– Tomás Palamás
Dec 3 at 22:33
($Leftarrow$)Now suppose the edges $e_1,dots ,e_k$ induce a graph with no cycle (what is this called?). Hint: Use this, if G is a graph on $n$ vertices and has $l$ components then the rank of $I(G)=n-l$.
– Tomás Palamás
Dec 3 at 22:34