Convex polyhedra of doubly stochastic matrices. I. Applications of the permanent function |
| |
Authors: | Richard A Brualdi Peter M Gibson |
| |
Institution: | University of Wisconsin, Madison, Wisconsin 53706 USA;University of Alabama in Huntsville, Huntsville, Alabama 35807 USA |
| |
Abstract: | The permanent function is used to determine geometrical properties of the set of all n × n nonnegative doubly stochastic matrices. If is a face of , then corresponds to an n × n (0, 1)-matrix A, where the permanent of A is the number of vertices of . If A is fully indecomposable, then the dimension of equals σ(A) ? 2n + 1, where σ(A) is the number of 1's in A. The only two-dimensional faces of are triangles and rectangles. For n ? 6, has four types of three-dimensional faces. The facets of the faces of are characterized. Faces of which are simplices are determined. If is a face of which is two-neighborly but not a simplex, then has dimension 4 and six vertices. All k-dimensional faces with k + 2 vertices are determined. The maximum number of vertices of a k-dimensional face is 2k. All k-dimensional faces with at least 2k?1 + 1 vertices are determined. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|