Search

We introduce two classes of Hadamard matrices of Goethals-Seidel type and construct many matrices in these classes., Comment: 10 pages

This doctoral thesis covers several topics related to the construction and study of maximal determinant matrices with complex entries. The first three chapters are devoted to number-theoretic tools to prove the non-solvability of Gram matrix equations over certain fields, with a focus on combinatorial applications. Chapter 4 gives a survey on Butson-type Hadamard matrices, and shows an improved lower bound on primes $p$ for the existence of $BH(12p, p)$ matrices. Chapter 5 contains the main contributions of the thesis, where the maximal determinant problem for matrices over the m-th roots of unity is discussed, and where new upper and lower bounds, as well as constructions at small orders, are given. Chapter 6 studies maximal determinant matrices over association schemes. Chapter 7 gives an application of design theory to privacy in communications, and it is connected to the rest of the thesis by the use of the theory of quadratic forms., Comment: 258 pages, 9 figures

Some combinatorial designs, such as Hadamard matrices, have been extensively researched and are familiar to readers across the spectrum of Science and Engineering. They arise in diverse fields such as cryptography, communication theory, and quantum computing. Objects like this also lend themselves to compelling mathematics problems, such as the Hadamard conjecture. However, complex generalized weighing matrices, which generalize Hadamard matrices, have not received anything like the same level of scrutiny. Motivated by an application to the construction of quantum error-correcting codes, which we outline in the latter sections of this paper, we survey the existing literature on complex generalized weighing matrices. We discuss and extend upon the known existence conditions and constructions, and compile known existence results for small parameters. Some interesting quantum codes are constructed to demonstrate their value., Comment: 33 pages including appendix

The smallest integer v>0 for which no skew-Hadamard matrix of order 4v is known is v=69. We show how to construct several such matrices. We also construct the first examples of symmetric Hadamard matrices of order 372., Comment: 5 pages

Let $m,n,s,k$ be four integers such that $3\leq s \leq n$, $3\leq k\leq m$ and $ms=nk$. Set $d=\gcd(s,k)$. In this paper we show how one can construct a Heffter array $H(m,n;s,k)$ starting from a square Heffter array $H(nk/d;d)$ whose elements belong to $d$ consecutive diagonals. As an example of application of this method, we prove that there exists an integer $H(m,n;s,k)$ in each of the following cases: $(i)$ $d\equiv 0 \pmod 4$; $(ii)$ $5\leq d\equiv 1 \pmod 4$ and $n k\equiv 3\pmod 4$; $(iii)$ $d\equiv 2 \pmod 4$ and $nk\equiv 0 \pmod 4$; $(iv)$ $d\equiv 3 \pmod 4$ and $n k\equiv 0,3\pmod 4$. The same method can be applied also for signed magic arrays $SMA(m,n;s,k)$ and for magic rectangles $MR(m,n;s,k)$. In fact, we prove that there exists an $SMA(m,n;s,k)$ when $d\geq 2$, and there exists an $MR(m,n;s,k)$ when either $d\geq 2$ is even or $d\geq 3$ and $nk$ are odd. We also provide constructions of integer Heffter arrays and signed magic arrays when $k$ is odd and $s\equiv 0 \pmod 4$.

The 1-product of matrices $S_1 \in \mathbb{R}^{m_1 \times n_1}$ and $S_2 \in \mathbb{R}^{m_2 \times n_2}$ is the matrix in $\mathbb{R}^{(m_1+m_2) \times (n_1n_2)}$ whose columns are the concatenation of each column of $S_1$ with each column of $S_2$. Our main result is a polynomial time algorithm for the following problem: given a matrix $S$, is $S$ a 1-product, up to permutation of rows and columns? Our main motivation is a close link between the 1-product of matrices and the Cartesian product of polytopes, which goes through the concept of slack matrix. Determining whether a given matrix is a slack matrix is an intriguing problem whose complexity is unknown, and our algorithm reduces the problem to irreducible instances. Our algorithm is based on minimizing a symmetric submodular function that expresses mutual information in information theory. We also give a polynomial time algorithm to recognize a more complicated matrix product, called the 2-product. Finally, as a corollary of our 1-product and 2-product recognition algorithms, we obtain a polynomial time algorithm to recognize slack matrices of $2$-level matroid base polytopes.

Consider a matrix $M$ chosen uniformly at random from a class of $m \times n$ matrices of zeros and ones with prescribed row and column sums. A partially filled matrix $D$ is a $\mathit{defining}$ $\mathit{set}$ for $M$ if $M$ is the unique member of its class that contains the entries in $D$. The $\mathit{size}$ of a defining set is the number of filled entries. A $\mathit{critical}$ $\mathit{set}$ is a defining set for which the removal of any entry stops it being a defining set. For some small fixed $\epsilon>0$, we assume that $n\le m=o(n^{1+\epsilon})$, and that $\lambda\le1/2$, where $\lambda$ is the proportion of entries of $M$ that equal $1$. We also assume that the row sums of $M$ do not vary by more than $\mathcal{O}(n^{1/2+\epsilon})$, and that the column sums do not vary by more than $\mathcal{O}(m^{1/2+\epsilon})$. Under these assumptions we show that $M$ almost surely has no defining set of size less than $\lambda mn-\mathcal{O}(m^{7/4+\epsilon})$. It follows that $M$ almost surely has no critical set of size more than $(1-\lambda)mn+\mathcal{O}(m^{7/4+\epsilon})$. Our results generalise a theorem of Cavenagh and Ramadurai, who examined the case when $\lambda=1/2$ and $n=m=2^k$ for an integer $k$.

An $n \times n$ matrix $H$ is Butson-Hadamard if its entries are $k^{\text{th}}$ roots of unity and it satisfies $HH^* = nI_n$. Write $BH(n, k)$ for the set of such matrices. Suppose that $k = p^{\alpha}q^{\beta}$ where $p$ and $q$ are primes and $\alpha \geq 1$. A recent result of {\"O}sterg{\aa}rd and Paavola uses a matrix $H \in BH(n,pk)$ to construct $H' \in BH(pn, k)$. We simplify the proof of this result and remove the restriction on the number of prime divisors of $k$. More precisely, we prove that if $k = mt$, and each prime divisor of $k$ divides $t$, then we can construct a matrix $H' \in BH(mn, t)$ from any $H \in BH(n,k)$., Comment: 5 pages

Let $v\geq6$ be an integer with $v\equiv2 \pmod 4$. In this paper, we introduce a new partitioning of the set of all $3$-subsets of a $v$-set into some simple trades.

Our main objective is to show that the computational methods that we previously developed to search for difference families in cyclic groups can be fully extended to the more general case of arbitrary finite abelian groups. In particular the power density PSD-test and the method of compression can be used to help the search., Comment: 18 pages, minor changes

For an integer $n\geq 1$, we display a poset $\Phi_n$ whose maximal chains are in bijection with the $n\times n$ alternating sign matrices. The Hasse diagram $\widehat \Phi_n$ is obtained from the $n$-cube by adding some edges. We show that the dihedral group $D_{2n}$ acts on $\widehat \Phi_n$ as a group of automorphisms., Comment: 6 pages

In this paper, we use two-variable Laurent polynomials attached to matrices to encode properties of compositions of sequences. The Lagrange identity in the ring of Laurent polynomials is then used to give a short and transparent proof of a theorem about the Yang multiplication., Comment: 9 pages, corrected typo

A Costas array is a permutation array for which the vectors joining pairs of $1$s are all distinct. We propose a new three-dimensional combinatorial object related to Costas arrays: an order $n$ Costas cube is an array $(d_{i,j,k})$ of size $n \times n \times n$ over $\mathbb{Z}_2$ for which each of the three projections of the array onto two dimensions, namely $(\sum_i d_{i,j,k})$ and $(\sum_j d_{i,j,k})$ and $(\sum_k d_{i,j,k})$, is an order $n$ Costas array. We determine all Costas cubes of order at most $29$, showing that Costas cubes exist for all these orders except $18$ and $19$ and that a significant proportion of the Costas arrays of certain orders occur as projections of Costas cubes. We then present constructions for four infinite families of Costas cubes., Comment: 12 pages, 1 figure. Theorem 11 introduces two further infinite families of Costas cubes

This work examines the concept of S-permutation matrices, namely $n^2 \times n^2$ permutation matrices containing a single 1 in each canonical $n \times n$ subsquare (block). The article suggests a formula for counting mutually disjoint pairs of $n^2 \times n^2$ S-permutation matrices in the general case by restricting this task to the problem of finding some numerical characteristics of the elements of specially defined for this purpose factor-set of the set of $n \times n$ binary matrices. The paper describe an algorithm that solves the main problem. To do that, every $n\times n$ binary matrix is represented uniquely as a n-tuple of integers., Comment: arXiv admin note: substantial text overlap with arXiv:1501.03395; text overlap with arXiv:1604.02691

In this paper, we study skew-symmetric $2$-$\{v;r,k;\lambda\}$ supplementary difference sets related to a certain class of complex spherical 2-codes. A classification of such supplementary difference sets is complete for $v \le 51$., Comment: 14 pages

A 0/1-simplex is the convex hull of n+1 affinely independent vertices of the unit n-cube I^n. It is nonobtuse if none its dihedral angles is obtuse, and acute if additionally none of them is right. Acute 0/1-simplices in I^n can be represented by 0/1-matrices P of size n x n whose Gramians have an inverse that is strictly diagonally dominant, with negative off-diagonal entries. In this paper, we will prove that the positive part D of the transposed inverse of P is doubly stochastic and has the same support as P. The negated negative part C of P^-T is strictly row-substochastic and its support is complementary to that of D, showing that P^-T=D-C has no zero entries and has positive row sums. As a consequence, for each facet F of an acute 0/1-facet S there exists at most one other acute 0/1-simplex T in I^n having F as a facet. We call T the acute neighbor of S at F. If P represents a 0/1-simplex that is merely nonobtuse, P^-T can have entries equal to zero. Its positive part D is still doubly stochastic, but its support may be strictly contained in the support of P. This allows P to be partly decomposable. In theory, this might cause a nonobtuse 0/1-simplex S to have several nonobtuse neighbors at each of its facets. Next, we study nonobtuse 0/1-simplices S having a partly decomposable matrix representation P. We prove that such a simplex also has a block diagonal matrix representation with at least two diagonal blocks, and show that a nonobtuse simplex with partly decomposable matrix representation can be split in mutually orthogonal fully indecomposable simplicial facets whose dimensions add up to n. Using this insight, we are able to extend the one neighbor theorem for acute simplices to a larger class of nonobtuse simplices., Comment: 26 pages, 17 figures

\textit{Propus} (which means twins) is a construction method for orthogonal $\pm 1$ matrices based on a variation of the Williamson array called the \textit{propus array} \[ \begin{matrix*}[r] A& B & B & D B& D & -A &-B B& -A & -D & B D& -B & B &-A. \end{matrix*} \] This construction designed to find symmetric Hadamard matrices was originally based on circulant symmetric $\pm 1$ matrices, called \textit{propus matrices}. We also give another construction based on symmetric Williamson-type matrices. We give constructions to find symmetric propus-Hadamard matrices for 57 orders $4n$, $n < 200$ odd. We give variations of the above array to allow for more general matrices than symmetric Williamson propus matrices. One such is the \textit{ Generalized Propus Array (GP)}., Comment: 13 pages, 19 figures

We give some very interesting matrices which are orthogonal over groups and, as far as we know, referenced, but in fact undocumented. This note is not intended to be published but available for archival reasons., Comment: 15 pages

A $Cretan(4t+1)$ matrix, of order $4t+1$, is an orthogonal matrix whose elements have moduli $\leq 1$. The only $Cretan(4t+1)$ matrices previously published are for orders 5, 9, 13, 17 and 37. This paper gives infinitely many new $Cretan(4t+1)$ matrices constructed using $regular~Hadamard$ matrices, $SBIBD(4t+1,k,\lambda)$, weighing matrices, generalized Hadamard matrices and the Kronecker product. We introduce an inequality for the radius and give a construction for a Cretan matrix for every order $n \geq 3$., Comment: 16 pages, 7 figures

Cretan matrices are orthogonal matrices with elements $\leq 1$. These may have application in forming some new materials. There is a search for Cretan matrices, especially with high determinant, for all orders. These have been found by both mathematical and computational methods. This paper highlights the differences between theoretical and computational solutions to finding Cretan matrices. It has been shown that the incidence matrix of a symmetric balanced incomplete block design can be used to form Cretan($v;2$) matrices. We give families of Cretan matrices constructed using Hadamard related difference sets., Comment: 16 pages, 3 figures, 1 table. arXiv admin note: text overlap with arXiv:1501.07012

We study orthogonal matrices whose elements have moduli $\leq 1$. This paper shows that the existence of two such families of matrices is equivalent. Specifically we show that the existence of an Hadamard matrix of order $4t$ is equivalent to the existence of a Cretan$(4t-1,2)$-Mersenne matrix., Comment: 9 pages, 1 Figure

One of the most promising structural approaches to resolving the Hadamard Conjecture uses the family of cocyclic matrices over ${\mathbb Z} _t \times {\mathbb Z}_2^2$. Two types of equivalence relations for classifying cocyclic matrices over ${\mathbb Z} _t \times {\mathbb Z}_2^2$ have been found. Any cocyclic matrix equivalent by either of these relations to a Hadamard matrix will also be Hadamard. One type, based on algebraic relations between cocycles over any finite group, has been known for some time. Recently, and independently, a second type, based on four geometric relations between diagrammatic visualisations of cocyclic matrices over ${\mathbb Z} _t \times {\mathbb Z}_2^2$, has been found. Here we translate the algebraic equivalences to diagrammatic equivalences and show one of the diagrammatic equivalences cannot be obtained this way. This additional equivalence is shown to be the geometric translation of matrix transposition., Comment: 12 pages

We consider a series of configurations defined by fibers of a given base configuration. We prove that Markov degree of the configurations is bounded from above by the Markov complexity of the base configuration. As important examples of base configurations we consider incidence matrices of graphs and study the maximum Markov degree of configurations defined by fibers of the incidence matrices. In particular we give a proof that the Markov degree for two-way transportation polytopes is three., Comment: 28 pages

An algorithm for obtaining all n\times n binary matrices having exactly 2 units in every row and every column is described in the paper. After analysing the work of the algorithm a formula for calculating the number of these matrices has been obtained. This formula is known and has been obtained using other methods, which by their nature are purely analytical and not constructive. Thus a new, constructive proof of this known formula has been obtained.

We give a new characterization of skew Hadamard matrices of size $n$ in terms of the data of the spectra of tournaments of size $n-2$., Comment: 9 pages

A characterization of $\mathbb{Z} _t \times \mathbb{Z}_2^2$-cocyclic Hadamard matrices is described, depending on the notions of {\em distributions}, {\em ingredients} and {\em recipes}. In particular, these notions lead to the establishment of some bounds on the number and distribution of 2-coboundaries over $\mathbb{Z}_t \times \mathbb{Z} _2^2$ to use and the way in which they have to be combined in order to obtain a $\mathbb{Z} _t \times \mathbb{Z}_2^2$-cocyclic Hadamard matrix. Exhaustive searches have been performed, so that the table in p. 132 in [4] is corrected and completed. Furthermore, we identify four different operations on the set of coboundaries defining $\mathbb{Z} _t \times \mathbb{Z}_2^2$-cocyclic matrices, which preserve orthogonality. We split the set of Hadamard matrices into disjoint orbits, define representatives for them and take advantage of this fact to compute them in an easier way than the usual purely exhaustive way, in terms of {\em diagrams}. Let ${\cal H}$ be the set of cocyclic Hadamard matrices over $\mathbb{Z}_t \times \mathbb{Z}_2^2$ having a symmetric diagram. We also prove that the set of Williamson type matrices is a subset of ${\cal H}$ of size $\frac{|{\cal H}|}{t}$., Comment: 19 pages (main paper) + 7 pages (Appendix); it is the result of merging arXiv:1112.4296 [math.CO] and arXiv:1112.4300 [math.CO] papers

In this paper we use a design theoretical approach to construct new, previously unknown complex Hadamard matrices. Our methods generalize and extend the earlier results of de la Harpe--Jones and Munemasa--Watatani and offer a theoretical explanation for the existence of some sporadic examples of complex Hadamard matrices in the existing literature. As it is increasingly difficult to distinguish inequivalent matrices from each other, we propose a new invariant, the fingerprint of complex Hadamard matrices. As a side result, we refute a conjecture of Koukouvinos et al. on (n-8)x(n-8) minors of real Hadamard matrices., Comment: 10 pages. To appear in Cryptography and Communications: Discrete Structures, Boolean Functions and Sequences

First we give an overview of the known supplementary difference sets (SDS) (A_i), i=1..4, with parameters (n;k_i;d), where k_i=|A_i| and each A_i is either symmetric or skew and k_1 + ... + k_4 = n + d. Five new Williamson matrices over the elementary abelian groups of order 25, 27 and 49 are constructed. New examples of skew Hadamard matrices of order 4n for n=47,61,127 are presented. The last of these is obtained from a (127,57,76)-difference family that we have constructed. An old non-published example of G-matrices of order 37 is also included., Comment: 16 pages, 2 tables. A few minor changes are made. The paper will appear in Operators and Matrices

We introduce a canonical form for near-normal sequences NN(n), and using it we enumerate the equivalence classes of such sequences for even n up to 30. These sequences are needed for Yang multiplication in the construction of longer T-sequences from base sequences., Comment: 13 pages, 1 table (over 5 pages long). Minor changes implemented

Strongly quadrangular matrices have been introduced in the study of the combinatorial properties of unitary matrices. It is known that if a (0, 1)-matrix supports a unitary then it is strongly quadrangular. However, the converse is not necessarily true. In this paper, we fully classify strongly quadrangular matrices up to degree 5. We prove that the smallest strongly quadrangular matrices which do not support unitaries have exactly degree 5. Further, we isolate two submatrices not allowing a (0, 1)-matrix to support unitaries., Comment: 11 pages, some typos are corrected. To appear in The Electronic journal of Linear Algebra

In the paper On the Existence of Hadamard Matrices in J. Combinatorial Theory 21, 1976, it is shown that for a natural number q > 3, we can construct an Hadamard Matrix of order 2^s q for s \geq t where t = [2 log_2(q-3)]. I will show that this bound is not a consequence of the proof given in the paper and explain the error in the argumentation., Comment: 3 pages

We construct several difference families on cyclic groups of orders 47 and 97, and use them to construct skew-Hadamard matrices of orders 188 and 388. Such difference families and matrices are constructed here for the first time. The matrices are constructed by using the Goethals-Seidel array., Comment: 7 pages, no figures, a paragraph added to the introduction, two misprints corrected. To appear in the International Mathematical Forum

We construct two Hadamard matrices of order 764. Both are of Goethals-Seidel type., Comment: 3 pages

Let S and T be vectors of positive integers with the same sum. We study the uniform distribution on the space of simple bipartite graphs with degree sequence S in one part and T in the other; equivalently, binary matrices with row sums S and column sums T. In particular, we find precise formulae for the probabilities that a given bipartite graph is edge-disjoint from, a subgraph of, or an induced subgraph of a random graph in the class. We also give similar formulae for the uniform distribution on the set of simple directed graphs with out-degrees S and in-degrees T. In each case, the graphs or digraphs are required to be sufficiently dense, with the degrees varying within certain limits, and the subgraphs are required to be sufficiently sparse. Previous results were restricted to spaces of sparse graphs. Our theorems are based on an enumeration of bipartite graphs avoiding a given set of edges, proved by multidimensional complex integration. As a sample application, we determine the expected permanent of a random binary matrix with row sums S and column sums T., Comment: Corrected the name of a cited author. A concise version has been accepted by Random Structures and Algorithms

The purpose of this paper is to introduce new parametric families of complex Hadamard matrices in two different ways. First, we prove that every real Hadamard matrix of order N>=4 admits an affine orbit. This settles a recent open problem of Tadej and Zyczkowski, who asked whether a real Hadamard matrix can be isolated among complex ones. In particular, we apply our construction to the only (up to equivalence) real Hadamard matrix of order 12 and show that the arising affine family is different from all previously known examples. Second, we recall a well-known construction related to real conference matrices, and show how to introduce an affine parameter in the arising complex Hadamard matrices. This leads to new parametric families of orders 10 and 14. An interesting feature of both of our constructions is that the arising families cannot be obtained via Dita's general method. Our results extend the recent catalogue of complex Hadamard matrices, and may lead to direct applications in quantum-information theory., Comment: 16 pages; Final version. Submitted to: European Journal of Combinatorics

Using reversible Hadamard difference sets, we construct symmetric Bush-type Hadamard matrices of order $4m^4$ for all odd integer $m$.

We study the question of finding the maximal determinant of matrices of odd order with entries {-1,1}. The most general upper bound on the maximal determinant, due to Barba, can only be achieved when the order is the sum of two consecutive squares. It is conjectured that the bound is always attained in such cases. Apart from these, only in orders 3, 7, 9, 11, 17 and 21 has the maximal value been established. In this paper we confirm the results for these orders, and add order 15 to the list. We follow previous authors in exhaustively searching for candidate Gram matrices having determinant greater than or equal to the square of a known lower bound on the maximum. We then attempt to decompose each candidate as the product of a {-1,1}-matrix and its transpose. For order 15 we find four candidates, all of Ehlich block form, two having determinant (105*3^5*2^14)^2 and the others determinant (108*3^5*2^14)^2. One of the former decomposes (in an essentially unique way) while the remaining three do not. This result proves a conjecture made independently by W. D. Smith and J. H. E. Cohn. We also use our method to compute improved upper bounds on the maximal determinant in orders 29, 33, and 37, and to establish the range of the determinant function of {-1,1}-matrices in orders 9 and 11., Comment: 30 pages

Let $P(d)$ be the probability that a random 0/1-matrix of size $d \times d$ is singular, and let $E(d)$ be the expected number of 0/1-vectors in the linear subspace spanned by d-1 random independent 0/1-vectors. (So $E(d)$ is the expected number of cube vertices on a random affine hyperplane spanned by vertices of the cube.) We prove that bounds on $P(d)$ are equivalent to bounds on $E(d)$: \[ P(d) = (2^{-d} E(d) + \frac{d^2}{2^{d+1}}) (1 + o(1)). \] We also report about computational experiments pertaining to these numbers., Comment: 9 pages

We report new world records for the maximal determinant of an n-by-n matrix with entries +/-1. Using various techniques, we beat existing records for n=22, 23, 27, 29, 31, 33, 34, 35, 39, 45, 47, 53, 63, 69, 73, 77, 79, 93, and 95, and we present the record-breaking matrices here. We conjecture that our n=22 value attains the globally maximizing determinant in its dimension. We also tabulate new records for n=67, 75, 83, 87, 91 and 99, dimensions for which no previous claims have been made. The relevant matrices in all these dimensions, along with other pertinent information, are posted at http://www.indiana.edu/~maxdet \., Comment: 20 pages; 15 are "figure-like" displays of matrices

A (partial) Latin square is a table of multiplication of a (partial) quasigroup. Multiplication of a (partial) quasigroup may be considered as a set of triples. We give a necessary and sufficient condition when a set of triples is a quotient of a (partial) Latin square., Comment: 8 pages, 2 figures