How would I prove that the determinant reduced Laplacian of a graph is independent of the choice of $i$?
$begingroup$
My homework problem gives us the definition of the Laplacian matrix $L(G)$ of the graph (the degree matrix minus the adjacency matrix) and the reduced Laplacian $L^i(G)$ (remove the $i^{th}$ row and column from the Laplacian) and asks us to prove that $det(L^i(G))$ is independent of the choice for $i$ if $G$ is simple and connected. I've written out the Laplacian for several graphs and convinced myself empirically that it's true, but I don't know how to start proving it in the general case. I also noticed that adding up any row or column will give us 0, which is pretty intuitively clear as the degree of a vertex is the sum of the neighbors, and so you'd end up with as many $-1$s in the rows or columns as the degree. But don't know how this result helps me.
Any suggestions?
Thanks!
linear-algebra graph-theory graph-laplacian
edited Jan 22 '15 at 3:43
hardmath
29k95298
asked Oct 3 '13 at 19:02
walkarwalkar
2,4661024
$endgroup$
add a comment |
$begingroup$
My homework problem gives us the definition of the Laplacian matrix $L(G)$ of the graph (the degree matrix minus the adjacency matrix) and the reduced Laplacian $L^i(G)$ (remove the $i^{th}$ row and column from the Laplacian) and asks us to prove that $det(L^i(G))$ is independent of the choice for $i$ if $G$ is simple and connected. I've written out the Laplacian for several graphs and convinced myself empirically that it's true, but I don't know how to start proving it in the general case. I also noticed that adding up any row or column will give us 0, which is pretty intuitively clear as the degree of a vertex is the sum of the neighbors, and so you'd end up with as many $-1$s in the rows or columns as the degree. But don't know how this result helps me.
Any suggestions?
Thanks!
linear-algebra graph-theory graph-laplacian
edited Jan 22 '15 at 3:43
hardmath
29k95298
asked Oct 3 '13 at 19:02
walkarwalkar
2,4661024
$endgroup$
add a comment |
$begingroup$
My homework problem gives us the definition of the Laplacian matrix $L(G)$ of the graph (the degree matrix minus the adjacency matrix) and the reduced Laplacian $L^i(G)$ (remove the $i^{th}$ row and column from the Laplacian) and asks us to prove that $det(L^i(G))$ is independent of the choice for $i$ if $G$ is simple and connected. I've written out the Laplacian for several graphs and convinced myself empirically that it's true, but I don't know how to start proving it in the general case. I also noticed that adding up any row or column will give us 0, which is pretty intuitively clear as the degree of a vertex is the sum of the neighbors, and so you'd end up with as many $-1$s in the rows or columns as the degree. But don't know how this result helps me.
Any suggestions?
Thanks!
linear-algebra graph-theory graph-laplacian
edited Jan 22 '15 at 3:43
hardmath
29k95298
asked Oct 3 '13 at 19:02
walkarwalkar
2,4661024
$endgroup$
My homework problem gives us the definition of the Laplacian matrix $L(G)$ of the graph (the degree matrix minus the adjacency matrix) and the reduced Laplacian $L^i(G)$ (remove the $i^{th}$ row and column from the Laplacian) and asks us to prove that $det(L^i(G))$ is independent of the choice for $i$ if $G$ is simple and connected. I've written out the Laplacian for several graphs and convinced myself empirically that it's true, but I don't know how to start proving it in the general case. I also noticed that adding up any row or column will give us 0, which is pretty intuitively clear as the degree of a vertex is the sum of the neighbors, and so you'd end up with as many $-1$s in the rows or columns as the degree. But don't know how this result helps me.
Any suggestions?
Thanks!
linear-algebra graph-theory graph-laplacian
linear-algebra graph-theory graph-laplacian
edited Jan 22 '15 at 3:43
hardmath
29k95298
asked Oct 3 '13 at 19:02
walkarwalkar
2,4661024
edited Jan 22 '15 at 3:43
hardmath
29k95298
asked Oct 3 '13 at 19:02
walkarwalkar
2,4661024
edited Jan 22 '15 at 3:43
hardmath
29k95298
edited Jan 22 '15 at 3:43
hardmath
29k95298
edited Jan 22 '15 at 3:43
hardmath
29k95298
29k95298
asked Oct 3 '13 at 19:02
walkarwalkar
2,4661024
asked Oct 3 '13 at 19:02
walkarwalkar
2,4661024
asked Oct 3 '13 at 19:02
walkarwalkar
2,4661024
2,4661024
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
This is in fact Kirchhoff's theorem which states that $$det(L^{i}(G)) = tau(G)$$ where $tau(G)$ is the number of spanning trees of $G.$
If this is not a sufficient argument let me know and I can prove the fact by more concrete means. The key in proving this is to observe that $L(G) = D(G)D(G)^t$ where $D(G)$ is the incidence matrix of $G.$
edited Dec 10 '18 at 18:52
Zach Langley
9731019
answered Oct 3 '13 at 19:17
JernejJernej
2,8211939
$endgroup$
$begingroup$
This kind of our first exposure to turning graphs into matrices, and we haven't used incidence matrices or anything like that. Would there be another way to prove it?
$endgroup$
– walkar
Oct 3 '13 at 19:22
$begingroup$
What is wrong with using Kirchhoff theorem then? You can quickly prove it using induction. See mathoverflow.net/questions/73385/…
$endgroup$
– Jernej
Oct 3 '13 at 19:25
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%2f513773%2fhow-would-i-prove-that-the-determinant-reduced-laplacian-of-a-graph-is-independe%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$
This is in fact Kirchhoff's theorem which states that $$det(L^{i}(G)) = tau(G)$$ where $tau(G)$ is the number of spanning trees of $G.$
If this is not a sufficient argument let me know and I can prove the fact by more concrete means. The key in proving this is to observe that $L(G) = D(G)D(G)^t$ where $D(G)$ is the incidence matrix of $G.$
edited Dec 10 '18 at 18:52
Zach Langley
9731019
answered Oct 3 '13 at 19:17
JernejJernej
2,8211939
$endgroup$
$begingroup$
This kind of our first exposure to turning graphs into matrices, and we haven't used incidence matrices or anything like that. Would there be another way to prove it?
$endgroup$
– walkar
Oct 3 '13 at 19:22
$begingroup$
What is wrong with using Kirchhoff theorem then? You can quickly prove it using induction. See mathoverflow.net/questions/73385/…
$endgroup$
– Jernej
Oct 3 '13 at 19:25
add a comment |
$begingroup$
This is in fact Kirchhoff's theorem which states that $$det(L^{i}(G)) = tau(G)$$ where $tau(G)$ is the number of spanning trees of $G.$
If this is not a sufficient argument let me know and I can prove the fact by more concrete means. The key in proving this is to observe that $L(G) = D(G)D(G)^t$ where $D(G)$ is the incidence matrix of $G.$
edited Dec 10 '18 at 18:52
Zach Langley
9731019
answered Oct 3 '13 at 19:17
JernejJernej
2,8211939
$endgroup$
$begingroup$
This kind of our first exposure to turning graphs into matrices, and we haven't used incidence matrices or anything like that. Would there be another way to prove it?
$endgroup$
– walkar
Oct 3 '13 at 19:22
$begingroup$
What is wrong with using Kirchhoff theorem then? You can quickly prove it using induction. See mathoverflow.net/questions/73385/…
$endgroup$
– Jernej
Oct 3 '13 at 19:25
add a comment |
$begingroup$
This is in fact Kirchhoff's theorem which states that $$det(L^{i}(G)) = tau(G)$$ where $tau(G)$ is the number of spanning trees of $G.$
If this is not a sufficient argument let me know and I can prove the fact by more concrete means. The key in proving this is to observe that $L(G) = D(G)D(G)^t$ where $D(G)$ is the incidence matrix of $G.$
edited Dec 10 '18 at 18:52
Zach Langley
9731019
answered Oct 3 '13 at 19:17
JernejJernej
2,8211939
$endgroup$
This is in fact Kirchhoff's theorem which states that $$det(L^{i}(G)) = tau(G)$$ where $tau(G)$ is the number of spanning trees of $G.$
If this is not a sufficient argument let me know and I can prove the fact by more concrete means. The key in proving this is to observe that $L(G) = D(G)D(G)^t$ where $D(G)$ is the incidence matrix of $G.$
edited Dec 10 '18 at 18:52
Zach Langley
9731019
answered Oct 3 '13 at 19:17
JernejJernej
2,8211939
edited Dec 10 '18 at 18:52
Zach Langley
9731019
edited Dec 10 '18 at 18:52
Zach Langley
9731019
edited Dec 10 '18 at 18:52
Zach Langley
9731019
9731019
answered Oct 3 '13 at 19:17
JernejJernej
2,8211939
answered Oct 3 '13 at 19:17
JernejJernej
2,8211939
answered Oct 3 '13 at 19:17
JernejJernej
2,8211939
2,8211939
$begingroup$
This kind of our first exposure to turning graphs into matrices, and we haven't used incidence matrices or anything like that. Would there be another way to prove it?
$endgroup$
– walkar
Oct 3 '13 at 19:22
$begingroup$
What is wrong with using Kirchhoff theorem then? You can quickly prove it using induction. See mathoverflow.net/questions/73385/…
$endgroup$
– Jernej
Oct 3 '13 at 19:25
add a comment |
$begingroup$
This kind of our first exposure to turning graphs into matrices, and we haven't used incidence matrices or anything like that. Would there be another way to prove it?
$endgroup$
– walkar
Oct 3 '13 at 19:22
$begingroup$
What is wrong with using Kirchhoff theorem then? You can quickly prove it using induction. See mathoverflow.net/questions/73385/…
$endgroup$
– Jernej
Oct 3 '13 at 19:25
$begingroup$
This kind of our first exposure to turning graphs into matrices, and we haven't used incidence matrices or anything like that. Would there be another way to prove it?
$endgroup$
– walkar
Oct 3 '13 at 19:22
$begingroup$
This kind of our first exposure to turning graphs into matrices, and we haven't used incidence matrices or anything like that. Would there be another way to prove it?
$endgroup$
– walkar
Oct 3 '13 at 19:22
$begingroup$
What is wrong with using Kirchhoff theorem then? You can quickly prove it using induction. See mathoverflow.net/questions/73385/…
$endgroup$
– Jernej
Oct 3 '13 at 19:25
$begingroup$
What is wrong with using Kirchhoff theorem then? You can quickly prove it using induction. See mathoverflow.net/questions/73385/…
$endgroup$
– Jernej
Oct 3 '13 at 19:25
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%2f513773%2fhow-would-i-prove-that-the-determinant-reduced-laplacian-of-a-graph-is-independe%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
