How to plot a graph from its incidence matrix?
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.
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
andIncidenceGraph
deal with relationships between vertices and edges of a graph, so you can't useIncidenceGraph
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.
Update:
It is still not quite clear to me what you are trying to do, so I'll go ahead with a few guesses. You say,
$X$ is a set of vertices, and $\mathcal{A}$ is a set of blocks. A block is a set of vertices.
I will assume that this incidence matrix described a bipartite graph of blocks and vertices, i.e. it tells us which vertex is a member of which block. Then I will assume that two vertices are connected if they are a member of the same block.
With IGraph/M, we can do this to get the bipartite graph:
bg = IGBipartiteIncidenceGraph@{{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}}
Then project it to get the block-block and the vertex-vertex relationships:
IGBipartiteProjections[bg]
Without IGraph/M, we could do e.g. this:
imat = {{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}};
am = Unitize[Transpose[imat].imat];
AdjacencyGraph[
am - IdentityMatrix@Length[am] (* get rid of diagonal *)
]
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}