University of Twente Student Theses


Implementation of Balanced Matrix Recognition Algorithms

Kraaij, H.J.L. (2023) Implementation of Balanced Matrix Recognition Algorithms.

[img] PDF
Abstract:A {0,±1} matrix is balanced if it does not contain a square submatrix with two nonzero elements per row and column in which the sum of all entries is 2 modulo 4. G. Zambelli provided a polynomial algorithm to test balancedness of a matrix. This paper discusses the algorithm and its implementation, and compares it against a naive approach using an exponential algorithm. The running time of the polynomial algorithm is O(n^9) for {0, 1} matrices and O(n^11) for {0,±1} matrices, where n is the number of rows and columns of the input matrix.
Item Type:Essay (Bachelor)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics
Programme:Applied Mathematics BSc (56965)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page