graphFromSlackMatrix -- creates the vertex-edge incidence matrix for the bipartite non-incidence graph with adjacency matrix the given slack matrix

Synopsis

Usage:

A = graphFromSlackMatrix S
Inputs:
- S, a matrix, a (symbolic) slack matrix
Outputs:
- A, a matrix, 0-1 vertex-edge incidence matrix

Description

This function creates a matrix whose columns correspond to the edges of the non-incidence graph of a slack matrix. They are ordered by variable index. The first n rows correspond to rows of the slack matrix (vertices/ground set elements) and the remaining rows correspond to columns of the slack matrix (facets/hyperplanes).

i1 : V = {{0, 0}, {1, 0}, {1, 1}, {0, 1}};

i2 : S = symbolicSlackMatrix V

Order of vertices is 
{{0, 0}, {1, 0}, {0, 1}, {1, 1}}

o2 = | 0   x_0 0   x_1 |
     | x_2 0   0   x_3 |
     | 0   x_4 x_5 0   |
     | x_6 0   x_7 0   |

                        4                 4
o2 : Matrix (QQ[x ..x ])  <-- (QQ[x ..x ])
                 0   7             0   7

i3 : A = graphFromSlackMatrix S
Graph computed from symbolic adjacency matrix: | 0   y_1 0   y_2 |
                                               | y_3 0   0   y_4 |
                                               | 0   y_5 y_6 0   |
                                               | y_7 0   y_8 0   |

o3 = | 1 1 0 0 0 0 0 0 |
     | 0 0 1 1 0 0 0 0 |
     | 0 0 0 0 1 1 0 0 |
     | 0 0 0 0 0 0 1 1 |
     | 0 0 1 0 0 0 1 0 |
     | 1 0 0 0 1 0 0 0 |
     | 0 0 0 0 0 1 0 1 |
     | 0 1 0 1 0 0 0 0 |

              8       8
o3 : Matrix ZZ  <-- ZZ

Caveat

If S is not a symbolic slack matrix, the columns of A will be ordered assuming edges are listed in order by rows of S (as in symbolicSlackMatrix).

Ways to use graphFromSlackMatrix:

graphFromSlackMatrix(Matrix)

For the programmer