Applying Graph Theory to Linear Algebra (not the other way around)How does one show a matrix is irreducible and reducible?Need help demonstrating a property of bilinear forms$K$ is a basis for $W$, and $L$ is a basis for $U$. Is $Kcup L$ is a basis for $U + W$?Images of basis vectors under injective linear map form a linearly independent setWhy doesn't a linearly independent set of image vectors imply an injection?Help on the relationship of a basis and a dual basisOn the importance of order for bases in finite dimensional vector spacesLinear Independence and Subset RelationsProof Related to the Span in linear algebra(Integer) Lattices: Proving Hadamard result $det(L) = prod_i=1^n ||b_i||$ if and only if $B$ is a basis of $L$ and an orthogonal basis of $V$Vector orthogonal to linear independent set of vectors is not in their span
Course development: can I pay someone to make slides for the course?
How to represent jealousy in a cute way?
Does a single fopen introduce TOCTOU vulnerability?
Why baskervald(x) is as semibold as default?
Is it advisable to add a location heads-up when a scene changes in a novel?
Are the guests in Westworld forbidden to tell the hosts that they are robots?
What is the "books received" section in journals?
Placement of positioning lights on A320 winglets
Print "N NE E SE S SW W NW"
Entered UK using my now-lost UK passport; can I go to Spain using my US passport?
Is it true that "only photographers care about noise"?
Forgot passport for Alaska cruise (Anchorage to Vancouver)
How to make a composition of functions prettier?
In The Incredibles 2, why does Screenslaver's name use a pun on something that doesn't exist in the 1950s pastiche?
How do I type a hyphen in iOS 12?
Is Jesus the last Prophet?
Why vspace-lineskip removes space after tikz picture although it stands before the picture?
What class is best to play when a level behind the rest of the party?
What plausible reason could I give for my FTL drive only working in space
Is tuition reimbursement a good idea if you have to stay with the job
Suppose leased car is totalled: what are financial implications?
How strong someone should be in order to fly without servo assisted hydraulics?
Recording Spectral Lines at Home
Why are ambiguous grammars bad?
Applying Graph Theory to Linear Algebra (not the other way around)
How does one show a matrix is irreducible and reducible?Need help demonstrating a property of bilinear forms$K$ is a basis for $W$, and $L$ is a basis for $U$. Is $Kcup L$ is a basis for $U + W$?Images of basis vectors under injective linear map form a linearly independent setWhy doesn't a linearly independent set of image vectors imply an injection?Help on the relationship of a basis and a dual basisOn the importance of order for bases in finite dimensional vector spacesLinear Independence and Subset RelationsProof Related to the Span in linear algebra(Integer) Lattices: Proving Hadamard result $det(L) = prod_i=1^n ||b_i||$ if and only if $B$ is a basis of $L$ and an orthogonal basis of $V$Vector orthogonal to linear independent set of vectors is not in their span
$begingroup$
I know about applications of Linear Algebra to Graph Theory, I find them boring. What interests me is whether one can draw graph-like pictures of linear functions to understand them better.
Do you know of any results like that?
I have one particular question I would like to know the answer to:
Let $f : V rightarrow V$ be a linear function and $b_1,...,b_n in V$ a basis of $V$. Also for every $v in V$ define $v_1,...,v_n$ so that $v_1 b_1 + ... + v_n b_n = v$.
Finally let $G = (B,E)$ be the graph with $B = b_1,...,b_n$ and $E = (b_i, b_j) text with weight f(b_i)_j mid i,j in 1,...,n $.
In words: draw a circle for every basis element and connect them so that you can see how $f$ maps the basis elements to each other.
Now delete all weights that are zero and assume the other weights are positive. Can we say something like: There is a cycle in $G$ if and only if $f$ has an eigenvector? To me that sounds like the Perron–Frobenius theorem
.
I'm also wondering if one could prove the existence of Jordan-Normal-Forms using graphs like this. (generalized eigenvectors are then maybe cycles connected by a tree)
In general I feel like there should be a graph-theoretic perspective on the (basic) concepts I've seen in linear algebra. What do you think?
linear-algebra graph-theory
asked Jun 5 at 2:15
SomeNameSomeName
865
New contributor
SomeName is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
|
show 3 more comments
$begingroup$
I know about applications of Linear Algebra to Graph Theory, I find them boring. What interests me is whether one can draw graph-like pictures of linear functions to understand them better.
Do you know of any results like that?
I have one particular question I would like to know the answer to:
Let $f : V rightarrow V$ be a linear function and $b_1,...,b_n in V$ a basis of $V$. Also for every $v in V$ define $v_1,...,v_n$ so that $v_1 b_1 + ... + v_n b_n = v$.
Finally let $G = (B,E)$ be the graph with $B = b_1,...,b_n$ and $E = (b_i, b_j) text with weight f(b_i)_j mid i,j in 1,...,n $.
In words: draw a circle for every basis element and connect them so that you can see how $f$ maps the basis elements to each other.
Now delete all weights that are zero and assume the other weights are positive. Can we say something like: There is a cycle in $G$ if and only if $f$ has an eigenvector? To me that sounds like the Perron–Frobenius theorem
.
I'm also wondering if one could prove the existence of Jordan-Normal-Forms using graphs like this. (generalized eigenvectors are then maybe cycles connected by a tree)
In general I feel like there should be a graph-theoretic perspective on the (basic) concepts I've seen in linear algebra. What do you think?
linear-algebra graph-theory
asked Jun 5 at 2:15
SomeNameSomeName
865
New contributor
SomeName is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
1
$begingroup$
Every linear map from a finite-dimensional vector space (over $mathbb C$) to itself has eigenvectors.
$endgroup$
– Robert Israel
Jun 5 at 3:43
1
$begingroup$
But you are correct that the generalized Perron-Frobenius theorem for non-negative matrices is related to this directed graph.
$endgroup$
– Robert Israel
Jun 5 at 3:45
$begingroup$
@RobertIsrael "But you are correct that the generalized Perron-Frobenius theorem for non-negative matrices is related to this directed graph. " - Really? Where could I read about that?
$endgroup$
– SomeName
Jun 5 at 9:39
1
$begingroup$
Did you notice the link to Wikipedia?
$endgroup$
– Robert Israel
Jun 5 at 12:23
$begingroup$
@RobertIsrael Oh I didn't, thank you!
$endgroup$
– SomeName
Jun 5 at 15:20
|
show 3 more comments
$begingroup$
I know about applications of Linear Algebra to Graph Theory, I find them boring. What interests me is whether one can draw graph-like pictures of linear functions to understand them better.
Do you know of any results like that?
I have one particular question I would like to know the answer to:
Let $f : V rightarrow V$ be a linear function and $b_1,...,b_n in V$ a basis of $V$. Also for every $v in V$ define $v_1,...,v_n$ so that $v_1 b_1 + ... + v_n b_n = v$.
Finally let $G = (B,E)$ be the graph with $B = b_1,...,b_n$ and $E = (b_i, b_j) text with weight f(b_i)_j mid i,j in 1,...,n $.
In words: draw a circle for every basis element and connect them so that you can see how $f$ maps the basis elements to each other.
Now delete all weights that are zero and assume the other weights are positive. Can we say something like: There is a cycle in $G$ if and only if $f$ has an eigenvector? To me that sounds like the Perron–Frobenius theorem
.
I'm also wondering if one could prove the existence of Jordan-Normal-Forms using graphs like this. (generalized eigenvectors are then maybe cycles connected by a tree)
In general I feel like there should be a graph-theoretic perspective on the (basic) concepts I've seen in linear algebra. What do you think?
linear-algebra graph-theory
asked Jun 5 at 2:15
SomeNameSomeName
865
New contributor
SomeName is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
I know about applications of Linear Algebra to Graph Theory, I find them boring. What interests me is whether one can draw graph-like pictures of linear functions to understand them better.
Do you know of any results like that?
I have one particular question I would like to know the answer to:
Let $f : V rightarrow V$ be a linear function and $b_1,...,b_n in V$ a basis of $V$. Also for every $v in V$ define $v_1,...,v_n$ so that $v_1 b_1 + ... + v_n b_n = v$.
Finally let $G = (B,E)$ be the graph with $B = b_1,...,b_n$ and $E = (b_i, b_j) text with weight f(b_i)_j mid i,j in 1,...,n $.
In words: draw a circle for every basis element and connect them so that you can see how $f$ maps the basis elements to each other.
Now delete all weights that are zero and assume the other weights are positive. Can we say something like: There is a cycle in $G$ if and only if $f$ has an eigenvector? To me that sounds like the Perron–Frobenius theorem
.
I'm also wondering if one could prove the existence of Jordan-Normal-Forms using graphs like this. (generalized eigenvectors are then maybe cycles connected by a tree)
In general I feel like there should be a graph-theoretic perspective on the (basic) concepts I've seen in linear algebra. What do you think?
linear-algebra graph-theory
linear-algebra graph-theory
asked Jun 5 at 2:15
SomeNameSomeName
865
New contributor
SomeName is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Jun 5 at 2:15
SomeNameSomeName
865
New contributor
SomeName is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited yesterday
SomeName
asked Jun 5 at 2:15
SomeNameSomeName
865
New contributor
SomeName is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Jun 5 at 2:15
SomeNameSomeName
865
asked Jun 5 at 2:15
SomeNameSomeName
865
865
New contributor
SomeName is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
SomeName is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
1
$begingroup$
Every linear map from a finite-dimensional vector space (over $mathbb C$) to itself has eigenvectors.
$endgroup$
– Robert Israel
Jun 5 at 3:43
1
$begingroup$
But you are correct that the generalized Perron-Frobenius theorem for non-negative matrices is related to this directed graph.
$endgroup$
– Robert Israel
Jun 5 at 3:45
$begingroup$
@RobertIsrael "But you are correct that the generalized Perron-Frobenius theorem for non-negative matrices is related to this directed graph. " - Really? Where could I read about that?
$endgroup$
– SomeName
Jun 5 at 9:39
1
$begingroup$
Did you notice the link to Wikipedia?
$endgroup$
– Robert Israel
Jun 5 at 12:23
$begingroup$
@RobertIsrael Oh I didn't, thank you!
$endgroup$
– SomeName
Jun 5 at 15:20
|
show 3 more comments
1
$begingroup$
Every linear map from a finite-dimensional vector space (over $mathbb C$) to itself has eigenvectors.
$endgroup$
– Robert Israel
Jun 5 at 3:43
1
$begingroup$
But you are correct that the generalized Perron-Frobenius theorem for non-negative matrices is related to this directed graph.
$endgroup$
– Robert Israel
Jun 5 at 3:45
$begingroup$
@RobertIsrael "But you are correct that the generalized Perron-Frobenius theorem for non-negative matrices is related to this directed graph. " - Really? Where could I read about that?
$endgroup$
– SomeName
Jun 5 at 9:39
1
$begingroup$
Did you notice the link to Wikipedia?
$endgroup$
– Robert Israel
Jun 5 at 12:23
$begingroup$
@RobertIsrael Oh I didn't, thank you!
$endgroup$
– SomeName
Jun 5 at 15:20
1
1
$begingroup$
Every linear map from a finite-dimensional vector space (over $mathbb C$) to itself has eigenvectors.
$endgroup$
– Robert Israel
Jun 5 at 3:43
$begingroup$
Every linear map from a finite-dimensional vector space (over $mathbb C$) to itself has eigenvectors.
$endgroup$
– Robert Israel
Jun 5 at 3:43
1
1
$begingroup$
But you are correct that the generalized Perron-Frobenius theorem for non-negative matrices is related to this directed graph.
$endgroup$
– Robert Israel
Jun 5 at 3:45
$begingroup$
But you are correct that the generalized Perron-Frobenius theorem for non-negative matrices is related to this directed graph.
$endgroup$
– Robert Israel
Jun 5 at 3:45
$begingroup$
@RobertIsrael "But you are correct that the generalized Perron-Frobenius theorem for non-negative matrices is related to this directed graph. " - Really? Where could I read about that?
$endgroup$
– SomeName
Jun 5 at 9:39
$begingroup$
@RobertIsrael "But you are correct that the generalized Perron-Frobenius theorem for non-negative matrices is related to this directed graph. " - Really? Where could I read about that?
$endgroup$
– SomeName
Jun 5 at 9:39
1
1
$begingroup$
Did you notice the link to Wikipedia?
$endgroup$
– Robert Israel
Jun 5 at 12:23
$begingroup$
Did you notice the link to Wikipedia?
$endgroup$
– Robert Israel
Jun 5 at 12:23
$begingroup$
@RobertIsrael Oh I didn't, thank you!
$endgroup$
– SomeName
Jun 5 at 15:20
$begingroup$
@RobertIsrael Oh I didn't, thank you!
$endgroup$
– SomeName
Jun 5 at 15:20
|
show 3 more comments
2 Answers
2
active
oldest
votes
$begingroup$
To build off of littleO's answer, the applications of graph theory to applied numerical linear algebra are incredibly extensive and I figured I'd add a bit more.
Associated to every $ntimes n$ matrix $A$ is a graph $G$ whose vertices are $1,2,ldots,n$ and for which $(i,j)$ is a directed edge iff $A_ij ne 0$. As littleO mentioned, if $G$ is chordal, then there exists an elimination ordering such that $A$'s Cholesky factorization can be computed with no fill-in.
Even if $G$ is not chordal, understanding the graph structure $G$ can help find much better elimination orders. Finding the best elimination order for a general graph $G$ is NP-hard. However, for certain classes of graphs, much can be said about their optimal elimination orderings based on graph-theoretic arguments. For instance, for planar graphs, the computational complexity of performing Gaussian elimination on an $ntimes n$ can at best be done with on the order of $sim n^3/2$ operations (see, for instance, here and here). This involves a clever combinatorial graph theoretic argument. Similar results hold for "higher dimensional" graphs, although this becomes more subtle.
Let me rattle off a few more. Perfect matchings, bipartite graphs, and strongly connected components all play a big role in doing elimination intelligently for nonsymmetric matrices. (These slides are a nice place to start.) There are weighted bipartite matching algorithms for preconditioning. The very active area of Laplacian solvers use graph theoretic techniques to try to solve special linear systems super fast. There's also a very interesting area of research where graph theoretic algorithms are modeled as matrix problems over certain semirings. (This may be more of an application of linear algebra to graph theory, but it's cool to me none-the-less.) As an upshot, graph theoretic ideas are all over the field of numerical linear algebra, as many matrices that merge in practice are very sparse and thus have interesting graph theoretic structures necessary to develop fast algorithms.
answered Jun 5 at 7:15
eepperly16eepperly16
3,51611227
$endgroup$
add a comment |
$begingroup$
The idea of a chordal graph is useful in numerical linear algebra. If an invertible matrix has a chordal sparsity pattern, then it has a Cholesky factorization with no fill-in (so that sparsity is not lost -- the Cholesky factors are just as sparse as the original matrix).
answered Jun 5 at 2:43
littleOlittleO
31.7k651114
$endgroup$
2
$begingroup$
For anyone who cares: seas.ucla.edu/~vandenbe/publications/chordalsdp.pdf
$endgroup$
– SomeName
Jun 5 at 2:50
add a comment |
Your Answer
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
);
);
SomeName is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3251408%2fapplying-graph-theory-to-linear-algebra-not-the-other-way-around%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
To build off of littleO's answer, the applications of graph theory to applied numerical linear algebra are incredibly extensive and I figured I'd add a bit more.
Associated to every $ntimes n$ matrix $A$ is a graph $G$ whose vertices are $1,2,ldots,n$ and for which $(i,j)$ is a directed edge iff $A_ij ne 0$. As littleO mentioned, if $G$ is chordal, then there exists an elimination ordering such that $A$'s Cholesky factorization can be computed with no fill-in.
Even if $G$ is not chordal, understanding the graph structure $G$ can help find much better elimination orders. Finding the best elimination order for a general graph $G$ is NP-hard. However, for certain classes of graphs, much can be said about their optimal elimination orderings based on graph-theoretic arguments. For instance, for planar graphs, the computational complexity of performing Gaussian elimination on an $ntimes n$ can at best be done with on the order of $sim n^3/2$ operations (see, for instance, here and here). This involves a clever combinatorial graph theoretic argument. Similar results hold for "higher dimensional" graphs, although this becomes more subtle.
Let me rattle off a few more. Perfect matchings, bipartite graphs, and strongly connected components all play a big role in doing elimination intelligently for nonsymmetric matrices. (These slides are a nice place to start.) There are weighted bipartite matching algorithms for preconditioning. The very active area of Laplacian solvers use graph theoretic techniques to try to solve special linear systems super fast. There's also a very interesting area of research where graph theoretic algorithms are modeled as matrix problems over certain semirings. (This may be more of an application of linear algebra to graph theory, but it's cool to me none-the-less.) As an upshot, graph theoretic ideas are all over the field of numerical linear algebra, as many matrices that merge in practice are very sparse and thus have interesting graph theoretic structures necessary to develop fast algorithms.
answered Jun 5 at 7:15
eepperly16eepperly16
3,51611227
$endgroup$
add a comment |
$begingroup$
To build off of littleO's answer, the applications of graph theory to applied numerical linear algebra are incredibly extensive and I figured I'd add a bit more.
Associated to every $ntimes n$ matrix $A$ is a graph $G$ whose vertices are $1,2,ldots,n$ and for which $(i,j)$ is a directed edge iff $A_ij ne 0$. As littleO mentioned, if $G$ is chordal, then there exists an elimination ordering such that $A$'s Cholesky factorization can be computed with no fill-in.
Even if $G$ is not chordal, understanding the graph structure $G$ can help find much better elimination orders. Finding the best elimination order for a general graph $G$ is NP-hard. However, for certain classes of graphs, much can be said about their optimal elimination orderings based on graph-theoretic arguments. For instance, for planar graphs, the computational complexity of performing Gaussian elimination on an $ntimes n$ can at best be done with on the order of $sim n^3/2$ operations (see, for instance, here and here). This involves a clever combinatorial graph theoretic argument. Similar results hold for "higher dimensional" graphs, although this becomes more subtle.
Let me rattle off a few more. Perfect matchings, bipartite graphs, and strongly connected components all play a big role in doing elimination intelligently for nonsymmetric matrices. (These slides are a nice place to start.) There are weighted bipartite matching algorithms for preconditioning. The very active area of Laplacian solvers use graph theoretic techniques to try to solve special linear systems super fast. There's also a very interesting area of research where graph theoretic algorithms are modeled as matrix problems over certain semirings. (This may be more of an application of linear algebra to graph theory, but it's cool to me none-the-less.) As an upshot, graph theoretic ideas are all over the field of numerical linear algebra, as many matrices that merge in practice are very sparse and thus have interesting graph theoretic structures necessary to develop fast algorithms.
answered Jun 5 at 7:15
eepperly16eepperly16
3,51611227
$endgroup$
add a comment |
$begingroup$
To build off of littleO's answer, the applications of graph theory to applied numerical linear algebra are incredibly extensive and I figured I'd add a bit more.
Associated to every $ntimes n$ matrix $A$ is a graph $G$ whose vertices are $1,2,ldots,n$ and for which $(i,j)$ is a directed edge iff $A_ij ne 0$. As littleO mentioned, if $G$ is chordal, then there exists an elimination ordering such that $A$'s Cholesky factorization can be computed with no fill-in.
Even if $G$ is not chordal, understanding the graph structure $G$ can help find much better elimination orders. Finding the best elimination order for a general graph $G$ is NP-hard. However, for certain classes of graphs, much can be said about their optimal elimination orderings based on graph-theoretic arguments. For instance, for planar graphs, the computational complexity of performing Gaussian elimination on an $ntimes n$ can at best be done with on the order of $sim n^3/2$ operations (see, for instance, here and here). This involves a clever combinatorial graph theoretic argument. Similar results hold for "higher dimensional" graphs, although this becomes more subtle.
Let me rattle off a few more. Perfect matchings, bipartite graphs, and strongly connected components all play a big role in doing elimination intelligently for nonsymmetric matrices. (These slides are a nice place to start.) There are weighted bipartite matching algorithms for preconditioning. The very active area of Laplacian solvers use graph theoretic techniques to try to solve special linear systems super fast. There's also a very interesting area of research where graph theoretic algorithms are modeled as matrix problems over certain semirings. (This may be more of an application of linear algebra to graph theory, but it's cool to me none-the-less.) As an upshot, graph theoretic ideas are all over the field of numerical linear algebra, as many matrices that merge in practice are very sparse and thus have interesting graph theoretic structures necessary to develop fast algorithms.
answered Jun 5 at 7:15
eepperly16eepperly16
3,51611227
$endgroup$
To build off of littleO's answer, the applications of graph theory to applied numerical linear algebra are incredibly extensive and I figured I'd add a bit more.
Associated to every $ntimes n$ matrix $A$ is a graph $G$ whose vertices are $1,2,ldots,n$ and for which $(i,j)$ is a directed edge iff $A_ij ne 0$. As littleO mentioned, if $G$ is chordal, then there exists an elimination ordering such that $A$'s Cholesky factorization can be computed with no fill-in.
Even if $G$ is not chordal, understanding the graph structure $G$ can help find much better elimination orders. Finding the best elimination order for a general graph $G$ is NP-hard. However, for certain classes of graphs, much can be said about their optimal elimination orderings based on graph-theoretic arguments. For instance, for planar graphs, the computational complexity of performing Gaussian elimination on an $ntimes n$ can at best be done with on the order of $sim n^3/2$ operations (see, for instance, here and here). This involves a clever combinatorial graph theoretic argument. Similar results hold for "higher dimensional" graphs, although this becomes more subtle.
Let me rattle off a few more. Perfect matchings, bipartite graphs, and strongly connected components all play a big role in doing elimination intelligently for nonsymmetric matrices. (These slides are a nice place to start.) There are weighted bipartite matching algorithms for preconditioning. The very active area of Laplacian solvers use graph theoretic techniques to try to solve special linear systems super fast. There's also a very interesting area of research where graph theoretic algorithms are modeled as matrix problems over certain semirings. (This may be more of an application of linear algebra to graph theory, but it's cool to me none-the-less.) As an upshot, graph theoretic ideas are all over the field of numerical linear algebra, as many matrices that merge in practice are very sparse and thus have interesting graph theoretic structures necessary to develop fast algorithms.
answered Jun 5 at 7:15
eepperly16eepperly16
3,51611227
answered Jun 5 at 7:15
eepperly16eepperly16
3,51611227
answered Jun 5 at 7:15
eepperly16eepperly16
3,51611227
answered Jun 5 at 7:15
eepperly16eepperly16
3,51611227
3,51611227
add a comment |
add a comment |
$begingroup$
The idea of a chordal graph is useful in numerical linear algebra. If an invertible matrix has a chordal sparsity pattern, then it has a Cholesky factorization with no fill-in (so that sparsity is not lost -- the Cholesky factors are just as sparse as the original matrix).
answered Jun 5 at 2:43
littleOlittleO
31.7k651114
$endgroup$
2
$begingroup$
For anyone who cares: seas.ucla.edu/~vandenbe/publications/chordalsdp.pdf
$endgroup$
– SomeName
Jun 5 at 2:50
add a comment |
$begingroup$
The idea of a chordal graph is useful in numerical linear algebra. If an invertible matrix has a chordal sparsity pattern, then it has a Cholesky factorization with no fill-in (so that sparsity is not lost -- the Cholesky factors are just as sparse as the original matrix).
answered Jun 5 at 2:43
littleOlittleO
31.7k651114
$endgroup$
2
$begingroup$
For anyone who cares: seas.ucla.edu/~vandenbe/publications/chordalsdp.pdf
$endgroup$
– SomeName
Jun 5 at 2:50
add a comment |
$begingroup$
The idea of a chordal graph is useful in numerical linear algebra. If an invertible matrix has a chordal sparsity pattern, then it has a Cholesky factorization with no fill-in (so that sparsity is not lost -- the Cholesky factors are just as sparse as the original matrix).
answered Jun 5 at 2:43
littleOlittleO
31.7k651114
$endgroup$
The idea of a chordal graph is useful in numerical linear algebra. If an invertible matrix has a chordal sparsity pattern, then it has a Cholesky factorization with no fill-in (so that sparsity is not lost -- the Cholesky factors are just as sparse as the original matrix).
answered Jun 5 at 2:43
littleOlittleO
31.7k651114
answered Jun 5 at 2:43
littleOlittleO
31.7k651114
answered Jun 5 at 2:43
littleOlittleO
31.7k651114
answered Jun 5 at 2:43
littleOlittleO
31.7k651114
31.7k651114
2
$begingroup$
For anyone who cares: seas.ucla.edu/~vandenbe/publications/chordalsdp.pdf
$endgroup$
– SomeName
Jun 5 at 2:50
add a comment |
2
$begingroup$
For anyone who cares: seas.ucla.edu/~vandenbe/publications/chordalsdp.pdf
$endgroup$
– SomeName
Jun 5 at 2:50
2
2
$begingroup$
For anyone who cares: seas.ucla.edu/~vandenbe/publications/chordalsdp.pdf
$endgroup$
– SomeName
Jun 5 at 2:50
$begingroup$
For anyone who cares: seas.ucla.edu/~vandenbe/publications/chordalsdp.pdf
$endgroup$
– SomeName
Jun 5 at 2:50
add a comment |
SomeName is a new contributor. Be nice, and check out our Code of Conduct.
SomeName is a new contributor. Be nice, and check out our Code of Conduct.
SomeName is a new contributor. Be nice, and check out our Code of Conduct.
SomeName is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3251408%2fapplying-graph-theory-to-linear-algebra-not-the-other-way-around%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
1
$begingroup$
Every linear map from a finite-dimensional vector space (over $mathbb C$) to itself has eigenvectors.
$endgroup$
– Robert Israel
Jun 5 at 3:43
1
$begingroup$
But you are correct that the generalized Perron-Frobenius theorem for non-negative matrices is related to this directed graph.
$endgroup$
– Robert Israel
Jun 5 at 3:45
$begingroup$
@RobertIsrael "But you are correct that the generalized Perron-Frobenius theorem for non-negative matrices is related to this directed graph. " - Really? Where could I read about that?
$endgroup$
– SomeName
Jun 5 at 9:39
1
$begingroup$
Did you notice the link to Wikipedia?
$endgroup$
– Robert Israel
Jun 5 at 12:23
$begingroup$
@RobertIsrael Oh I didn't, thank you!
$endgroup$
– SomeName
Jun 5 at 15:20