University of Twente Student Theses
Implementation of Balanced Matrix Recognition Algorithms
Kraaij, H.J.L. (2023) Implementation of Balanced Matrix Recognition Algorithms.
|
PDF
1MB |
| 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: | https://purl.utwente.nl/essays/96341 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page