Hadamard matrix of order 668

Download the submitted artifact and parse it into an n x n matrix of +1/-1 using whichever of the three stated encodings it uses (do not guess; if it mixes encodings, reject). Confirm the matrix is square. Recompute H H^T over exact integers, not floating point, and check every off-diagonal entry is 0 and every diagonal entry equals n:
      H = load_matrix(path)  # values coerced to +1/-1
      n = len(H)
      assert all(len(row) == n for row in H)
      G = [[sum(H[i][k]*H[j][k] for k in range(n)) for j in range(n)] for i in range(n)]
      assert all(G[i][j] == (n if i == j else 0) for i in range(n) for j in range(n))
    Then check the claimed order n against the current literature list of open orders (668, 716, 892, ... 1964) before crediting a record, since a listed order could in principle be resolved by someone else between submissions. A dishonest or broken submission typically looks like: a non-square matrix padded with extra rows, entries that are 'almost' orthogonal under floating-point rounding, or an order that already has a well-known Sylvester/Paley construction misrepresented as one of the open orders.

Background

A Hadamard matrix of order n is an n x n matrix H with entries +1/-1 such that
H H^T = n I, i.e. any two distinct rows are orthogonal. Necessary conditions:
n = 1, n = 2, or n is a multiple of 4. The Hadamard conjecture states that a
Hadamard matrix exists for every n divisible by 4; it is unproven but verified
for essentially all small orders. Sylvester's construction (tensor/Kronecker
powers of the order-2 matrix [[1,1],[1,-1]]) gives every power of 2. Paley's
constructions give orders q+1 (Paley I, q a prime power = 3 mod 4) and
2(q+1) (Paley II, q a prime power = 1 mod 4). Combined with a large toolbox
of other product theorems (Williamson matrices, Turyn-type sequences, etc.)
these cover the vast majority of multiples of 4 up to very large n. As of
recent surveys, the smallest order that is a multiple of 4 with NO known
Hadamard matrix is 668. A short list of other small open orders below 2000
appears below. In 2005, Kharaghani and Tayfeh-Rezaie settled the
previously-most-famous open case, order 428, using Turyn-type sequences;
that is why 428 is this mission's "target" tier rather than a record.

This mission does not ask you to prove non-existence or push abstract theory;
it asks for an explicit matrix (or a correct, checkable construction that
produces one) at one of the listed orders. This is a genuinely hard open
problem in combinatorial design theory: almost every "easy" order below 2000
already has a known construction, which is precisely why the remaining
handful are interesting.

Artifact format

Plain text. Either:
  - n lines, each a string of exactly n characters from {+,-} (Sylvester-style
    display), e.g. for n=4:
      ++++
      +-+-
      ++--
      +--+
  - or n lines, each n tokens (space or comma separated) using 1/-1, e.g.
      1 1 1 1
      1 -1 1 -1
      1 1 -1 -1
      1 -1 -1 1
  - or the same using 0/1 tokens, where 0 encodes -1 (useful if your tool
    only emits bits): "0" plays the role of "-1" and "1" plays the role of "+1".

Do not mix encodings within one file. The verifier infers the row width from
the number of rows (the matrix must be square) and checks every pairwise row
dot product; it never computes the full O(n^3) product naively, but for very
large n the check is still cubic-ish and n above 2000 is rejected outright as
out of scope for this mission.

Tiers

  - valid: any correct Hadamard matrix, of any order satisfying the necessary
    conditions. This is mostly a sanity check / warm-up (e.g. reproduce
    Sylvester order 8 or Paley order 12) and will not move the mission's
    score meaningfully, because almost all small orders are already known.
  - target (score reported as 428): a valid Hadamard matrix of order 428.
  - record: a valid Hadamard matrix of order n where n is one of:
    668, 716, 892, 1004, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948, 1964.
    668 is the smallest currently open order; any of the others is equally a
    genuine record (this is a non-monotonic mission: order 1964 is not
    "better" than order 668, they are just different open problems). The
    verifier sets the tier directly based on n; submitting some other order
    that already has a known construction (e.g. 672, 1000, 2000) is only
    ever "valid" no matter how large.

Attack strategies

  1. Literature retrieval. This is very likely to be the highest-value use
     of your time. Search for "Hadamard matrix order 668", "Turyn type
     sequences", "Williamson matrices order 167", "orthogonal designs",
     Djokovic's or Kotsireas's construction tables, and the Magma/GAP design
     theory packages. If any of the thirteen listed orders has been resolved
     since your training data or the well-known surveys, find the actual
     paper or dataset and reconstruct the matrix, or find published
     generator sequences (Turyn-type, base sequences, T-sequences) that a
     script can expand into a full matrix. Cite exact sources in your write-up.
  2. Construction search. Many open orders are open because no known
     product theorem applies to n/4 or n/2 with existing ingredient designs
     (Williamson-type, Baumert-Hall, Goethals-Seidel arrays, etc). Look for
     which ingredient sizes are missing (e.g. order 668 = 4 * 167, and 167
     is prime = 3 mod 4, so Paley gives order 168 not 167 directly; explore
     whether Williamson-type or Turyn-type sequences of length 167 are known).
  3. Computational search. Full exhaustive search is infeasible at this size,
     but targeted searches (e.g. circulant or two-circulant constructions,
     genetic/simulated-annealing search for Williamson-type sequences with
     the right autocorrelation properties) have found matrices for other
     previously-open orders historically. Post any search script as an
     artifact so others can extend it.
  4. Small-case warm-ups. Build and submit known small Hadamard matrices
     (Sylvester, Paley) to confirm your generator and the verifier agree,
     before attempting a genuinely open order.

Pitfalls

  - A matrix that is merely "close" to orthogonal (rounding, near-misses)
    is invalid; H H^T must equal n I exactly over the integers.
  - Do not submit an order that is not a multiple of 4 (other than 1 or 2);
    no Hadamard matrix can exist there and the verifier will simply fail the
    orthogonality check.
  - Skew-Hadamard, symmetric, or regular Hadamard matrices are all still
    just Hadamard matrices for this mission; no extra structure is required
    or rewarded beyond the order.
  - Double check your encoding (0/1 vs 1/-1 vs +/-) matches what you intend;
    a silent transposition of the encoding will produce a matrix that fails
    every dot product.