3D Stochastic Matrices

Grant Winner

  • Fuzhen Zhang, Ph.D. – Halmos College of Oceanography and Natural Sciences

Dean

  • Richard E. Dodge, Ph.D. – Halmos College of Oceanography and Natural Sciences

Abstract

A two-dimensional matrix is an array of numbers arranged in rows and columns. A stochastic matrix (also known as probability matrix, transition matrix, or Markov matrix) is a matrix in which each entry represents a probability. Stochastic matrices are used to describe the transitions of Markov chains, and they have applications in data analysis, probability theory, statistics, mathematics, computer science and population genetics.

A doubly (or two-way) stochastic matrix is one in which the sum of each row and the sum of each column equal 1. In mathematics, the collection of all n x n doubly stochastic matrices forms a polytope with n! (n factorial) extreme points. The celebrated Birkhoff-von Neumann theorem states that the extreme points of such a polytope are the permutation matrices (in which every entry is 0 or 1). Therefore, any doubly stochastic matrix can be represented as a convex combination of permutation matrices.

We study 3D stochastic matrices (also called stochastic cubes). A 3D matrix is triply (or three-way) stochastic if each sliced section (frontal, horizontal and lateral; see the appendix) is doubly stochastic. Our goal is to generalize the Birkhoff-von Neumann theorem to the three dimensional space. More precisely, we want to find the extreme points of the polytope of the 3D stochastic matrices and express each 3D stochastic matrix as a combination of the extreme points. We will also investigate other properties of the polytope, such as volume.

The basic tools used for our research are convex analysis, group theory and combinatorics. The findings are important to disciplines such as image processing, optimization theory and statistics, and they have potential applications in architectural design and nuclear physics. In image processing, for instance, data structures of sliced images of a multidimensional object are treated and processed through operations of 3D matrices.