A344674 a(n) is the maximum value such that there is an n X n binary orthogonal matrix with every row having at least a(n) ones.

1, 1, 1, 3, 1, 5, 3, 7, 5, 9, 5, 11

Offset

1,4

Comments

The inverse of an orthogonal matrix is its transpose. This implies the dot product of a row with itself must be 1. This further implies the number of ones in each row must be odd. Given that orthogonal matrices form a group, it must be the case the transpose is also an orthogonal matrix. This requires every column of a binary orthogonal matrix also have an odd number of ones. As a result, there will always be an orthogonal matrix of size n X n having rows with n-1 number of ones if n is an even number, namely an all-ones matrix except for zeros down the main diagonal. An n X n orthogonal matrix cannot exist with n-1 ones in each row if n is odd, since n-1 is even.

a(n) = n-1 if n is even.

a(n) < n-1 if n is odd.

Links

Table of n, a(n) for n=1..12.

Example

There exist 10 X 10 binary orthogonal matrices such that every row has at least 9 ones, but no 10 X 10 binary orthogonal matrix exists with 10 ones in each row, so a(10) = 9.
There exist 9 X 9 binary orthogonal matrices such that every row has at least 5 ones, but no 9 X 9 binary orthogonal matrix exists with 6 or more ones in each row, so a(9) = 5.

Crossrefs

Cf. A003053.

Sequence in context: A318661 A089654 A233526 * A097062 A350948 A324894

Adjacent sequences: A344671 A344672 A344673 * A344675 A344676 A344677

Keyword

nonn,hard,more

Author

Nathan J. Russell, May 26 2021

Extensions

a(11)-a(12) from Martin Ehrenstein, Jun 17 2021

Status

approved