5
$\begingroup$

I'm using Mathematica v9 and am trying to draw a graph by using its 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.

enter image description here

How do I fix this?

$\endgroup$
6
  • 1
    $\begingroup$ 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? $\endgroup$
    – Szabolcs
    Jul 18, 2014 at 13:08
  • 1
    $\begingroup$ @Szabolcs Check [this definition].(i.imgur.com/ET0EBEk.png) $\endgroup$
    – Guinea Pig
    Jul 18, 2014 at 13:34
  • $\begingroup$ 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. $\endgroup$
    – Szabolcs
    Jul 18, 2014 at 13:42
  • $\begingroup$ @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. $\endgroup$
    – Guinea Pig
    Jul 18, 2014 at 14:00
  • 2
    $\begingroup$ Actually that makes is quite clear that your definition is completely different from Mathematica's definition ... why do you say it's the same? $\endgroup$
    – Szabolcs
    Jul 18, 2014 at 14:04

4 Answers 4

8
$\begingroup$

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]

enter image description here

and the incidence matrices:

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

enter image description here

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

$\endgroup$
7
  • $\begingroup$ @GuineaPig based on your math exchange link $\endgroup$
    – ubpdqn
    Jul 18, 2014 at 12:33
  • $\begingroup$ This is truly amazing. $\endgroup$
    – Guinea Pig
    Jul 18, 2014 at 14:50
  • $\begingroup$ @ubpdqn, so what does OP's matrix mean in relation to the final matrix, i.e. what do 11 columns of am stand for? I've failed to reconstruct it from the code :))) $\endgroup$
    – garej
    Feb 2, 2019 at 11:59
  • $\begingroup$ @garej see the hyperlink in the comments thread of question...it is a long time since I looked at this. Can’t remember. Link, as I recall, helped me understand OP $\endgroup$
    – ubpdqn
    Feb 2, 2019 at 12:03
  • $\begingroup$ @ubpdqn, I saw the link and it stays that first matrix is not a valid Incidence matrix of BIBD. (notice that it has different number of "1" in different columns). So what logic did you follow while building the code? $\endgroup$
    – garej
    Feb 3, 2019 at 6:36
8
$\begingroup$

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.


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}}

enter image description here

Then project it to get the block-block and the vertex-vertex relationships:

IGBipartiteProjections[bg]

enter image description here

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 *)
]

enter image description here

$\endgroup$
6
$\begingroup$

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}
$\endgroup$
5
  • $\begingroup$ That is strange... The text book said it is. Check this link. $\endgroup$
    – Guinea Pig
    Jul 18, 2014 at 10:22
  • $\begingroup$ Seems like IncidenceGraph can only draw a graph which edges are comprised in two vertices. BTW, my matrices are valid incidence matrix. $\endgroup$
    – Guinea Pig
    Jul 18, 2014 at 10:30
  • 1
    $\begingroup$ @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? $\endgroup$ Jul 18, 2014 at 10:42
  • $\begingroup$ 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. $\endgroup$
    – Guinea Pig
    Jul 18, 2014 at 10:49
  • $\begingroup$ 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.) $\endgroup$
    – Szabolcs
    Jul 18, 2014 at 15:28
5
$\begingroup$

The answer why it is not valid incidence matrix of BIBD (balanced incomplete block design) 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}};

GraphComputation`GraphExtensionDump`validIncidenceSparseArrayQ[m]
(* False *)

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

Edit: This is the incidence matrix of the regular pairwise balanced design. A pairwise balanced design (or PBD) is a design (X, A) such that every pair of distinct points is contained in exactly λ blocks, where λ is a positive integer. Furthermore, (X, A) is a regular pairwise balanced design if every point x ∈ X occurs in exactly r blocks of A, where r is a positive integer.

$\endgroup$
2
  • $\begingroup$ Seems like IncidenceGraph can only draw a graph which edges are comprised in two vertices. BTW, my matrices are valid incidence matrix. $\endgroup$
    – Guinea Pig
    Jul 18, 2014 at 10:30
  • $\begingroup$ 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. $\endgroup$
    – Szabolcs
    Jul 18, 2014 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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