Deletions and Collapsions with Partitioned Binary Matrices.

Document Type


Publication Date



It has been proven that, given any table of integers, one ? and only one ? of these statements is true: either some rows, excluding the first, can be deleted so that every column has an even sum, or some columns can be erased so that every row, excluding the first, has an even sum. I created a program which can be used to test whether this theorem holds true for a given matrix when the theorem is generalized to include partitions which must be either deleted or collapsed. Professor Naimi, in his ongoing research in the field of Low-Dimensional Topology, has developed a conjecture regarding the generalized theorem?s legitimacy. The project was largely successful; although there are still some minor glitches when the third conjecture is applied to certain matrices, we are reasonably certain that this problem does not stem from errors in the component functions, and thus should be quickly solved. This program will also be modified to search all possible matrix/partition combinations through to a matrix size of approximately 10x10. If this search yields a counterexample to the conjecture, then we have a disproof, and the project will be complete. Otherwise, the program will be used to compile a list of matrices for which only the third conjecture is true; this list is likely to aid in the search for a proof.


Ramin Naimi




National Science Foundation-Award for the Integration of Research and Education.

This document is currently not available here.