Can we say that vector of branches spans $(n-1)$ dimension space or incidence matrix rows (columns?) span...
$begingroup$
If we have connected graph and $mathbfPhi=(Phi_1,Phi_2...Phi_n)$ - nodes, and $phi_k=Phi_i-Phi_j$ so
$mathbf{phi}=(phi_1,phi_2...phi_N)$ - branches (edges), can we say that vector $mathbfphi$ spans $(n-1)$ dimensions space independent of $N$?
Also, if we know that $$mathbfphi=A^intercalmathbfPhi,$$
where $A$ - incidence matrix maybe it would be more right to say that incidence matrix rows (columns?) span $(n-1)$ dimensions space?
I've found a proof that $rank(A)le n-1$ but I don't understand 4.4.17. Would be grateful for clarification.
And I don't see how can we use this result for my question.
graph-theory vector-spaces
asked Dec 18 '18 at 14:09
TagTag
696
$endgroup$
add a comment |
$begingroup$
If we have connected graph and $mathbfPhi=(Phi_1,Phi_2...Phi_n)$ - nodes, and $phi_k=Phi_i-Phi_j$ so
$mathbf{phi}=(phi_1,phi_2...phi_N)$ - branches (edges), can we say that vector $mathbfphi$ spans $(n-1)$ dimensions space independent of $N$?
Also, if we know that $$mathbfphi=A^intercalmathbfPhi,$$
where $A$ - incidence matrix maybe it would be more right to say that incidence matrix rows (columns?) span $(n-1)$ dimensions space?
I've found a proof that $rank(A)le n-1$ but I don't understand 4.4.17. Would be grateful for clarification.
And I don't see how can we use this result for my question.
graph-theory vector-spaces
asked Dec 18 '18 at 14:09
TagTag
696
$endgroup$
add a comment |
$begingroup$
If we have connected graph and $mathbfPhi=(Phi_1,Phi_2...Phi_n)$ - nodes, and $phi_k=Phi_i-Phi_j$ so
$mathbf{phi}=(phi_1,phi_2...phi_N)$ - branches (edges), can we say that vector $mathbfphi$ spans $(n-1)$ dimensions space independent of $N$?
Also, if we know that $$mathbfphi=A^intercalmathbfPhi,$$
where $A$ - incidence matrix maybe it would be more right to say that incidence matrix rows (columns?) span $(n-1)$ dimensions space?
I've found a proof that $rank(A)le n-1$ but I don't understand 4.4.17. Would be grateful for clarification.
And I don't see how can we use this result for my question.
graph-theory vector-spaces
asked Dec 18 '18 at 14:09
TagTag
696
$endgroup$
If we have connected graph and $mathbfPhi=(Phi_1,Phi_2...Phi_n)$ - nodes, and $phi_k=Phi_i-Phi_j$ so
$mathbf{phi}=(phi_1,phi_2...phi_N)$ - branches (edges), can we say that vector $mathbfphi$ spans $(n-1)$ dimensions space independent of $N$?
Also, if we know that $$mathbfphi=A^intercalmathbfPhi,$$
where $A$ - incidence matrix maybe it would be more right to say that incidence matrix rows (columns?) span $(n-1)$ dimensions space?
I've found a proof that $rank(A)le n-1$ but I don't understand 4.4.17. Would be grateful for clarification.
And I don't see how can we use this result for my question.
graph-theory vector-spaces
graph-theory vector-spaces
asked Dec 18 '18 at 14:09
TagTag
696
asked Dec 18 '18 at 14:09
TagTag
696
edited Dec 18 '18 at 14:34
Tag
asked Dec 18 '18 at 14:09
TagTag
696
asked Dec 18 '18 at 14:09
TagTag
696
asked Dec 18 '18 at 14:09
TagTag
696
696
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Equation (4.4.17) is using the fundamental theorem of linear algebra, which in this case, since the columns of $E$ are elements of $mathbb{R}^n$ (I am using $n$ for the number of nodes, as you do in your question, while the book is using $m$), implies that $$ text{rank}(E^top) + text{dim} , N(E^top) = n. $$
Since the (nonzero) vector $e$ satisfies $E^top e = 0$, the dimension of the null space of $E^top$ is at least 1, we can conclude $$text{rank}(E)= text{rank}(E^top) le n-1.$$
Thus, the columns of the incidence matrix span a space of dimension at most $n-1$. As mentioned in the book, if the network is connected, then the columns of the incidence matrix span a space of dimension exactly $n-1$.
answered Dec 18 '18 at 14:43
VincenzoVincenzo
1916
$endgroup$
$begingroup$
Thanks for clarification. So it is not right to say that $phi$ spans such a space but it would be right to say that incidence matrix spans such a space? Also, I don't understand, we usually say that some set of vectors spans a space, isn't it more right to divide our incidence matrix in columns or rows?
$endgroup$
– Tag
Dec 18 '18 at 14:56
$begingroup$
Correct, I should have referred more precisely to the set of column vectors of the incidence matrix. I corrected the answer.
$endgroup$
– Vincenzo
Dec 18 '18 at 15:15
add a comment |
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',
autoActivateHeartbeat: false,
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
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3045204%2fcan-we-say-that-vector-of-branches-spans-n-1-dimension-space-or-incidence-ma%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
$begingroup$
Equation (4.4.17) is using the fundamental theorem of linear algebra, which in this case, since the columns of $E$ are elements of $mathbb{R}^n$ (I am using $n$ for the number of nodes, as you do in your question, while the book is using $m$), implies that $$ text{rank}(E^top) + text{dim} , N(E^top) = n. $$
Since the (nonzero) vector $e$ satisfies $E^top e = 0$, the dimension of the null space of $E^top$ is at least 1, we can conclude $$text{rank}(E)= text{rank}(E^top) le n-1.$$
Thus, the columns of the incidence matrix span a space of dimension at most $n-1$. As mentioned in the book, if the network is connected, then the columns of the incidence matrix span a space of dimension exactly $n-1$.
answered Dec 18 '18 at 14:43
VincenzoVincenzo
1916
$endgroup$
$begingroup$
Thanks for clarification. So it is not right to say that $phi$ spans such a space but it would be right to say that incidence matrix spans such a space? Also, I don't understand, we usually say that some set of vectors spans a space, isn't it more right to divide our incidence matrix in columns or rows?
$endgroup$
– Tag
Dec 18 '18 at 14:56
$begingroup$
Correct, I should have referred more precisely to the set of column vectors of the incidence matrix. I corrected the answer.
$endgroup$
– Vincenzo
Dec 18 '18 at 15:15
add a comment |
$begingroup$
Equation (4.4.17) is using the fundamental theorem of linear algebra, which in this case, since the columns of $E$ are elements of $mathbb{R}^n$ (I am using $n$ for the number of nodes, as you do in your question, while the book is using $m$), implies that $$ text{rank}(E^top) + text{dim} , N(E^top) = n. $$
Since the (nonzero) vector $e$ satisfies $E^top e = 0$, the dimension of the null space of $E^top$ is at least 1, we can conclude $$text{rank}(E)= text{rank}(E^top) le n-1.$$
Thus, the columns of the incidence matrix span a space of dimension at most $n-1$. As mentioned in the book, if the network is connected, then the columns of the incidence matrix span a space of dimension exactly $n-1$.
answered Dec 18 '18 at 14:43
VincenzoVincenzo
1916
$endgroup$
$begingroup$
Thanks for clarification. So it is not right to say that $phi$ spans such a space but it would be right to say that incidence matrix spans such a space? Also, I don't understand, we usually say that some set of vectors spans a space, isn't it more right to divide our incidence matrix in columns or rows?
$endgroup$
– Tag
Dec 18 '18 at 14:56
$begingroup$
Correct, I should have referred more precisely to the set of column vectors of the incidence matrix. I corrected the answer.
$endgroup$
– Vincenzo
Dec 18 '18 at 15:15
add a comment |
$begingroup$
Equation (4.4.17) is using the fundamental theorem of linear algebra, which in this case, since the columns of $E$ are elements of $mathbb{R}^n$ (I am using $n$ for the number of nodes, as you do in your question, while the book is using $m$), implies that $$ text{rank}(E^top) + text{dim} , N(E^top) = n. $$
Since the (nonzero) vector $e$ satisfies $E^top e = 0$, the dimension of the null space of $E^top$ is at least 1, we can conclude $$text{rank}(E)= text{rank}(E^top) le n-1.$$
Thus, the columns of the incidence matrix span a space of dimension at most $n-1$. As mentioned in the book, if the network is connected, then the columns of the incidence matrix span a space of dimension exactly $n-1$.
answered Dec 18 '18 at 14:43
VincenzoVincenzo
1916
$endgroup$
Equation (4.4.17) is using the fundamental theorem of linear algebra, which in this case, since the columns of $E$ are elements of $mathbb{R}^n$ (I am using $n$ for the number of nodes, as you do in your question, while the book is using $m$), implies that $$ text{rank}(E^top) + text{dim} , N(E^top) = n. $$
Since the (nonzero) vector $e$ satisfies $E^top e = 0$, the dimension of the null space of $E^top$ is at least 1, we can conclude $$text{rank}(E)= text{rank}(E^top) le n-1.$$
Thus, the columns of the incidence matrix span a space of dimension at most $n-1$. As mentioned in the book, if the network is connected, then the columns of the incidence matrix span a space of dimension exactly $n-1$.
answered Dec 18 '18 at 14:43
VincenzoVincenzo
1916
edited Dec 18 '18 at 18:14
answered Dec 18 '18 at 14:43
VincenzoVincenzo
1916
answered Dec 18 '18 at 14:43
VincenzoVincenzo
1916
answered Dec 18 '18 at 14:43
VincenzoVincenzo
1916
1916
$begingroup$
Thanks for clarification. So it is not right to say that $phi$ spans such a space but it would be right to say that incidence matrix spans such a space? Also, I don't understand, we usually say that some set of vectors spans a space, isn't it more right to divide our incidence matrix in columns or rows?
$endgroup$
– Tag
Dec 18 '18 at 14:56
$begingroup$
Correct, I should have referred more precisely to the set of column vectors of the incidence matrix. I corrected the answer.
$endgroup$
– Vincenzo
Dec 18 '18 at 15:15
add a comment |
$begingroup$
Thanks for clarification. So it is not right to say that $phi$ spans such a space but it would be right to say that incidence matrix spans such a space? Also, I don't understand, we usually say that some set of vectors spans a space, isn't it more right to divide our incidence matrix in columns or rows?
$endgroup$
– Tag
Dec 18 '18 at 14:56
$begingroup$
Correct, I should have referred more precisely to the set of column vectors of the incidence matrix. I corrected the answer.
$endgroup$
– Vincenzo
Dec 18 '18 at 15:15
$begingroup$
Thanks for clarification. So it is not right to say that $phi$ spans such a space but it would be right to say that incidence matrix spans such a space? Also, I don't understand, we usually say that some set of vectors spans a space, isn't it more right to divide our incidence matrix in columns or rows?
$endgroup$
– Tag
Dec 18 '18 at 14:56
$begingroup$
Thanks for clarification. So it is not right to say that $phi$ spans such a space but it would be right to say that incidence matrix spans such a space? Also, I don't understand, we usually say that some set of vectors spans a space, isn't it more right to divide our incidence matrix in columns or rows?
$endgroup$
– Tag
Dec 18 '18 at 14:56
$begingroup$
Correct, I should have referred more precisely to the set of column vectors of the incidence matrix. I corrected the answer.
$endgroup$
– Vincenzo
Dec 18 '18 at 15:15
$begingroup$
Correct, I should have referred more precisely to the set of column vectors of the incidence matrix. I corrected the answer.
$endgroup$
– Vincenzo
Dec 18 '18 at 15:15
add a comment |
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.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3045204%2fcan-we-say-that-vector-of-branches-spans-n-1-dimension-space-or-incidence-ma%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
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
