# How to plot a graph from it's incidence matrix?

I'm using Mathematica v9 and am trying to draw a graph by using it's incidence graph, but it won't draw it, which occurs an error "is not a valid incidence matrix.". But I've checked my matrix, and it's totally fine. I tried three matrices but error comes out every time.

Here are my matrices in input forms.

$6\times11$ incidence matrix:

({{1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0},
{1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
{1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1},
{0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0},
{0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0},
{0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1}})


$9\times12$ incidence matrix:

({{1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0},
{1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0},
{1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1},
{0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0},
{0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1},
{0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0},
{0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1},
{0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0},
{0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0}})


And here's a screenshot of my codes and their errors.

How do I fix this?

-
The terms "incidence matrix" is used for several completely different things. What do you mean by "incidence matrix" exactly? Are you working with bipartite graphs? –  Szabolcs Jul 18 '14 at 13:08
@Szabolcs Check [this definition].(i.imgur.com/ET0EBEk.png) –  Guinea Pig Jul 18 '14 at 13:34
I don't understand that definition fully because it relies on information presented earlier in the book. (What is $X$, what is $A$?) But it looks like it's not the same as Mathematica's definition. –  Szabolcs Jul 18 '14 at 13:42
@Szabolcs It is same. $X$ is a set of vertices, and $\mathcal{A}$ is a set of blocks. A block is a set of vertices. –  Guinea Pig Jul 18 '14 at 14:00
Actually that makes is quite clear that your definition is completely different from Mathematica's definition ... why do you say it's the same? –  Szabolcs Jul 18 '14 at 14:04

The test matrices are matrices but not incidence matrices. The rows represent the vertices and each column represents an edge. Consequently each column must have only 2 non-zero entries or a single entry of 2 for self loops. This is not the case for any of the matrices or their transposes.

To check for yourself, try yourself, e.g.:

mat = IncidenceMatrix[CompleteGraph[4]] // Normal
IncidenceGraph[mat]


The incidence matrix:

{{1, 1, 1, 0, 0, 0}, {1, 0, 0, 1, 1, 0}, {0, 1, 0, 1, 0, 1}, {0, 0, 1,
0, 1, 1}}


To see the matrix use MatrixForm on mat.

To use IncidenceGraph do not use MatrixForm.

For directed graphs the starting vertex has an entry -1 and the terminal vertex 1. You can also play this.

It is useful to look at the related concept of AdjacencyMatrix (which is necessarily square) and symmetric for undirected graphs.

UPDATE

As each answer has observed the supplied matrices are not incidence matrices based on standard documentation and Mathematica's documentation. However, based on some of the commentary I present the following as, perhaps, the graph that relates to this representation.

The test matrices:

a = {{1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 1, 1, 1, 0, 0,
0}, {1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1}, {0, 1, 1, 0, 0, 1, 0, 0,
1, 0, 0}, {0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0}, {0, 1, 0, 0, 1, 0, 0,
1, 0, 0, 1}};
ma = {{1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0}, {1, 0, 0, 0, 1, 0, 0, 1,
0, 0, 1, 0}, {1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1}, {0, 1, 0, 1, 0,
0, 0, 0, 1, 0, 1, 0}, {0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1}, {0,
1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0}, {0, 0, 1, 1, 0, 0, 0, 1, 0, 0,
0, 1}, {0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0}, {0, 0, 1, 0, 0, 1, 1,
0, 0, 0, 1, 0}};


The (perhaps) desired graph:

func[mt_] := Module[{s},
s = SparseArray[mt]["NonzeroPositions"];
Join @@ (UndirectedEdge @@@ Partition[First@Transpose[#], 2, 1] & /@
GatherBy[s, Last])]


Applying:

g1 = Graph[func[a], VertexSize -> 0.4,
VertexLabels -> Placed["Name", Center], VertexLabelStyle -> {20}]
g2 = Graph[func[ma], VertexSize -> 0.4,
VertexLabels -> Placed["Name", Center], VertexLabelStyle -> {20}]
vis = GraphicsGrid[{MatrixForm /@ {a, ma}, {Style["\[DownArrow]", 46],
Style["\[DownArrow]", 46]}, {g1, g2}}, Frame -> True,
ImageSize -> 600]


and the incidence matrices:

in = Grid[{MatrixForm /@ {a, ma}, {Style["\[DownArrow]", 46],
Style["\[DownArrow]", 46]},
MatrixForm[Normal@IncidenceMatrix[#]] & /@ {g1, g2}},
Frame -> True]


I may, of course, have misunderstood the relationship between the matrix and the desired graph.

-
@GuineaPig based on your math exchange link –  ubpdqn Jul 18 '14 at 12:33
This is truly amazing. –  Guinea Pig Jul 18 '14 at 14:50

The term incidence matrix has caused confusion on this site before, so I think it's time to clear this up.

There's no standard, generally agreed upon definition of incidence matrix. It's a loose term for a matrix that describes the relationship (connections) between two different classes of objects. What these objects are can vary.

When you see the term incidence matrix in a new context, always take a moment to look up the precise definition.

• In Mathematica, IncidenceMatrix and IncidenceGraph deal with relationships between vertices and edges of a graph, so you can't use IncidenceGraph with your matrix.

• Often, incidence matrix refers to the adjacency matrix of a bipartite graph of some sort.

• In the book you cite, the incidence matrix describes which vertex is part of which block. This is different from Mathematica's definition.

If you describe briefly what BIBD is and how these graphs are constructed precisely, I'll give you a function to reconstruct the graph from the type of incidence matrix you have.

-

Sorry, but your matrices aren't valid incidence matrices. From the IncidenceMatrix help page:

For an undirected graph, an entry $a_{ij}$ of the incidence matrix is given by:

• 0 if vertex $v_i$ is not incident to edge $e_j$

• 1 if vertex $v_i$ is incident to edge $e_j$

• 2 if vertex $v_i$ is incident to edge $e_j$ and a self-loop

In particular, this means that all the columns in an incidence matrix must sum to 2, as edges by definition connection two vertices (excluding loops, which your matrices don't have). Your matrices fail that test:

Total[{
{1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0},
{1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
{1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1},
{0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0},
{0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0},
{0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1}
}]

{3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2}

-
That is strange... The text book said it is. Check this link. –  Guinea Pig Jul 18 '14 at 10:22
Seems like IncidenceGraph can only draw a graph which edges are comprised in two vertices. BTW, my matrices are valid incidence matrix. –  Guinea Pig Jul 18 '14 at 10:30
@GuineaPig Hum, than your textbook must have a different definition of an incidence matrix. I'm intrigued though: how do you draw an edge between more than two vertices? –  Teake Nutma Jul 18 '14 at 10:42
The definition is same. But draw an edge between more that two vertices, that question is also my question xD It is very ambiguous. Check this link that I've posted about that yesterday, but no one has answered. –  Guinea Pig Jul 18 '14 at 10:49
As you suggest in your comment, there's no standard definition of incidence matrix, and the OP's definition doesn't match Mathematica's. (See my answer.) –  Szabolcs Jul 18 '14 at 15:28

The answer why it is not valid incidence matrix is given by the above answers.

To verify if your matrix is valid, use the following command

m = {{1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0},
{1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
{1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1},
{0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0},
{0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0},
{0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1}};

GraphComputationGraphExtensionDumpvalidIncidenceSparseArrayQ[m]
(* False *)


http://mathworld.wolfram.com/IncidenceMatrix.html

-
Seems like IncidenceGraph can only draw a graph which edges are comprised in two vertices. BTW, my matrices are valid incidence matrix. –  Guinea Pig Jul 18 '14 at 10:30
The MathWorld definition you cite is misleading in that it suggests that this is a generally accepted standard definition. It's not. "Incidence matrix" is used in various ways. Please see my answer. –  Szabolcs Jul 18 '14 at 15:27