2
$\begingroup$

How to define the graph of a square matrix $\mathbf{G}$ with real entries?

I know that given a graph $\Gamma(V, E)$, one can define its adjacency matrix $\mathbf{A}$. But given a matrix $\mathbf{G}$ how to define its graph?

P.S. I was reading in this book Matrix Analysis. There is a theorem that asserts that $\mathbf{A}$ is irreducible $\Leftrightarrow$ $\Gamma(\mathbf{A})$ is strongly connected (where $\Gamma(\mathbf{A})$is the graph of $\mathbf{A}$). I do not know what is the definiton of the graph of a square matrix.

$\endgroup$
  • 2
    $\begingroup$ In no expert in graph theory, but doesn't it depends on what your problem is ? For example you can consider that a square matrix $G$ with elements $G_{i,j}$ represents the graph ie : $G_{i,j}\neq 0$ iif $i$ and $j$ are connected, with a weight $G_{i,j}$ for this edge. $\endgroup$ – Bertrand R Apr 10 '14 at 21:41
  • $\begingroup$ I was reading in this book Matrix Analysis. There is a theorem that asserts that $\mathbf{A}$ is irreducible $\Leftrightarrow$ $\Gamma(\mathbf{A})$ is strongly connected (where $\Gamma(\mathbf{A})$is the graph of $\mathbf{A}$). I do not know what is the definiton of the graph of a square matrix. $\endgroup$ – zighalo Apr 10 '14 at 21:52
  • $\begingroup$ There are two binary matrices that are often associated with a given simple graph, the incidence matrix and the adjacency matrix. I would expect the book you are reading to define the notion of "the graph of a square matrix" to give a variation on the adjacency matrix, since these are always square. Perhaps you can add a page reference? $\endgroup$ – hardmath Aug 5 '17 at 17:13
  • $\begingroup$ Did you perhaps overlook Definition 6.2.11 in that book (page 399), which associates a directed graph $G$ with $n\times n$ square matrix $A$ having $n$ nodes with a directed edge from the $i$th node to the $j$th node whenever $a_{ij} \neq 0$? $\endgroup$ – hardmath Aug 6 '17 at 19:05
5
$\begingroup$

In this context, if the matrix is $n\times n$ we define a directed graph with vertex set $\{1,\ldots,n\}$, where there is an arc from $i$ to $j$ if $A_{i,j}\ne0$. This directed graph may have loops, but they do not affect whether the directed graph is strongly connected. It is not weighted.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.