Hadamard의 최대 결정 요인 문제

Hadamard's maximal determinant problem

Jacques Hadamard의 이름을 딴 Hadamard의 최대 결정요인 문제는 원소가 1 또는 -1인 행렬의 가장 큰 결정요인을 요구한다.원소가 0 또는 1인 행렬에 대한 유사한 질문은 아래와 같이 n 크기의 {1,-1} 행렬의 최대 결정 인수가 n-1 크기의 {0,1} 행렬의 최대 결정 인수의 2배이기n−1 때문에 동등하다.이 문제는 1893년 논문에서[1] Hadamard에 의해 제기되었는데, Hadamard는 이 논문에서 그의 유명한 결정요인을 제시했고 일반 크기의 행렬에 대해 미해결 상태로 남아있다.Hadamard의 바운드는 n 크기의 {1, -1}-수치에 최대 n의n/2 결정 요인이 있음을 암시한다.하다마드는 실베스터의[2] 구조가 n이 2의 검정력일 때 바운드를 얻는 행렬의 예를 만들어 낸다고 관찰하고, 12와 20 사이즈의 자기 자신의 예를 만들어냈다.그는 또한 n이 1, 2 또는 4의 배수일 때에만 바운드가 달성 가능하다는 것을 보여주었다.추가적인 예들은 나중에 스카피스와 핼리 그리고 그 후 많은 다른 작가들에 의해 구성되었다.그러한 행렬은 현재 Hadamard 행렬로 알려져 있다.그들은 집중적인 연구를 받았다.

n ≡ 1, 2, 3 (mod 4)이 덜 주목 받은 매트릭스 크기 n.가장 이른 결과는 하다마드의 n 홀수 구속을 조였던 바르바와 n=3, 5, 6, 7의 가장 큰 결정요인을 발견한 윌리엄슨 덕분이다.몇 가지 중요한 결과는 다음과 같다.

  • Barba, Ehlich, Wojtas로 인해 더 엄격한 경계는 n ≡ 1, 2, 3 (mod 4)에 대해, 그러나 항상 달성할 수 있는 것은 아니라고 알려져 있다.
  • n ≡ 1 또는 2(mod 4)의 한계에 도달하는 행렬의 몇 가지 무한 시퀀스
  • 특정 n ≡ 1 또는 2에 대한 한계에 도달하는 행렬 수(모드 4)
  • 특정 n ≡ 1 또는 3 (모드 4)에 대한 한계에 도달하지 못했지만, 전체 계산에 의해 최대 결정 인자를 갖는 것으로 입증된 다수의 행렬.

통계에서 실험의 설계는 정보 매트릭스 XX가T 최대 결정 인자를 갖는 {1, -1}개의 행렬 X(필수 제곱은 아님)를 사용한다. (XT 표기법은 X의 전치점을 의미한다.)그러한 행렬을 D-최적 설계라고 한다.[3]X가 제곱 행렬이면 포화 D-최적 설계로 알려져 있다.

하다마드 행렬

n×n Hadamard 행렬의 두 행은 직교한다.{1, -1} 행렬의 경우, 이는 두 행이 항목의 정확히 절반에서 서로 다르다는 것을 의미하며, n이 홀수 숫자일 때는 불가능하다.n ≡ 2 (모드 4)일 때, 둘 다 세 번째 행에 직교하는 두 행은 서로 직교할 수 없다.이러한 문장은 n = 1, 2 또는 4의 배수인 경우에만 n×n Hadamard 행렬이 존재할 수 있음을 의미한다.Hadamard 행렬은 잘 연구되었지만, 4의 양의 배수인 n마다 n×n Hadamard 행렬이 존재하는지 여부는 알려져 있지 않다.n×n Hadamard 행렬이 존재하지 않는 가장 작은 n은 668이다.

{1, -1} 행렬의 동등성 및 정규화

{1, -1} 매트릭스 R에서 수행되는 다음 작업 중 하나는 마이너스 부호로만 R의 결정 인자를 변경한다.

  • 행의 부정.
  • 열의 부정.
  • 두 줄로 교차한다.
  • 두 열 교환.

상기 연산의 어떤 순서에 의해 R을1 R로2 변환할 수 있다면 두 개의 {1,-1} 행렬인 R과1 R은2 동등한 것으로 간주된다.등가 행렬의 결정요인은 부호변경을 제외하고 동일하며 행과 열의 부정과 순열로 R을 표준화하는 것이 편리한 경우가 많다.첫 번째 행과 열의 모든 요소가 1이면 {1, -1} 행렬이 정규화된다.행렬의 크기가 홀수일 경우, 각 행과 열에 짝수 수의 원소 1과 홀수 수의 원소 -1이 포함된 다른 정규화를 사용하는 것이 유용할 수 있다.이러한 정규화 중 하나는 처음 두 작업을 사용하여 수행할 수 있다.

{1, -1} 및 {0, 1} 행렬에 대한 최대 결정 요인 문제의 연결

정규화된 n×n {1, -1} 행렬 집합에서 (n-1)×(n-1)×(n-1) {0, 1} 행렬 집합에 이르는 일대일 지도가 있으며, 그 아래 결정 인자의 크기가1−n 2배 감소한다.이 지도는 다음과 같은 단계로 구성되어 있다.

  1. 2행부터 n행까지의 행에서 {1, -1} 행렬의 1행을 빼십시오(결정 인자는 변경되지 않음).
  2. 2행 ~ n행 및 2열 ~ n열로 구성된 (n-1)×(n-1) 서브트리렉스를 추출한다.이 행렬에는 원소 0과 -2가 있다. (이 하위 행렬의 결정 인자는 1단계에서 얻은 행렬의 1열에 대해 공 인자 확장을 수행함으로써 알 수 있듯이 원래 행렬의 결정 인자와 동일하다.)
  3. {0, 1} 행렬을 얻으려면 서브트릭스를 -2로 나눈다(-2로 결정 인자를 곱함).1−n

예:

이 예에서 원본 매트릭스는 결정인자 -16을 가지며, 영상에는 결정인자 2 = -16·(-2)가 있다.−3

{0, 1} 행렬의 결정요인은 정수이므로, n×n {1, -1} 행렬의 결정요인은 2의n−1 정수배수다.

최대 결정 인자의 상한

그램 매트릭스

R을 n by n {1, -1} 행렬로 한다.R의 Gram 행렬은 G = RRT 행렬로 정의된다.이 정의에서 그것은 G를 따른다.

  1. 정수 행렬,
  2. 대칭이지만
  3. 양성화합성피느산염이고
  4. 값이 n인 상수 대각선을 가지고 있다.

R의 행을 부정하거나 그 행에 순열을 적용하면 동일한 부정과 순열이 G의 행과 해당 열에 모두 적용된다.우리는 또한 행렬 G′=RRR을T 정의할 수 있다.행렬 G는 벡터 집합의 일반적인 Gram 행렬로, R 행 집합에서 파생된 Gram 행렬인 반면, G′은 R. A 행렬 R의 열 집합에서 파생된 Gram 행렬로 G = G′은 정규 행렬이다.알려진 모든 최대 결정 행렬은 정상 행렬과 동등하지만 이것이 항상 그런 것인지는 알려져 있지 않다.

하다마드의 묶음(모두 n)

Hadamard의 경계는 det R = (상세 G)1/2 ≤ (상세 nI)1/2 = n이라는n/2 점에 주목함으로써 도출할 수 있으며, 이는 내가 n by n ID 매트릭스인 nI가 1-4를 만족하는 행렬 중 최대 결정 인자의 고유 행렬이라는 관측의 결과물이다.이 멈춤쇠 R은 2의n−1 정수 배수여야 하며, Hadamard의 구속이 항상 달성할 수 있는 것은 아니라는 또 다른 입증에 사용될 수 있다.n이 홀수일 때, 바운드 n은n/2 비정수 또는 홀수일 때, 따라서 n = 1인 경우를 제외하고 달성할 수 없다.n = 2k, k 홀수일 때, 2가 Hadamard의 바운드를 나눈 최고 힘은 2이며k n = 2가 아닌 한 2보다n−1 작다.따라서 하다마드의 바운드는 n = 1, 2 또는 4의 배수가 아니면 달성할 수 없다.

바바는 n 괴짜로 되어 있다.

n이 홀수일 때 그램 행렬의 속성 1은 다음과 같이 강화될 수 있다.

  1. G는 홀수 정수의 행렬이다.

이를 통해 더 날카로운 상한을[4] 도출할 수 있다: det R = (dete G)1/2 ≤ (det (n-1)I+J)1/2 = (2n-1)(1/2n-1) 여기서 J는 올원 행렬이다.(n−1)/2여기서 (n-1)I+J는 수정된 속성 1과 속성 2-4를 만족하는 최대 결정 행렬이다.행 집합과 해당 열 집합의 최대 곱하기까지 -1이 유일하다.경계는 2n-1이 완전한 사각형이 아니면 달성할 수 없으며, 따라서 n ≡ 3 (모드 4)에서는 결코 달성할 수 없다.

N ≡ 2 (모드 4)행 Elrich-Wojtas행

n이 짝수일 때, R의 행 집합을 두 개의 하위 집합으로 분할할 수 있다.

  • 짝수 유형의 행은 짝수 수의 원소 1과 짝수 수의 원소 -1을 포함한다.
  • 홀수 유형의 행은 홀수 수의 원소 1과 홀수 수의 원소 -1을 포함한다.

같은 유형의 두 행의 도트 제품은 n(mod 4)에 합치하고, 반대 유형의 두 행의 도트 제품은 n+2(mod 4)에 합치한다.n ≡ 2 (mod 4)는 R의 행을 허용함으로써 표준 형태를 가정할 수 있음을 의미한다.

여기서 A와 D는 원소가 2(모드 4)로 합치되는 대칭 정수 행렬이고, B는 원소가 0(모드 4)으로 합치되는 행렬이다.1964년에 Ehlich와[5] Wojtas는[6] 독립적으로 이 형태의 최대 결정 행렬에서 A와 D는 모두 n/2 크기이고 (n-2)I+2J와 같은 반면 B는 0 행렬이라는 것을 보여주었다.이 최적의 형태는 행 집합과 해당 열의 집합이 -1만큼 곱하고 행과 열에 순열을 동시에 적용하는 독특한 형태다.이는 바운드 데트 R ≤(2n-2)(n-2)을 의미한다.(n−2)/2Ehlich는 R이 바운드에 도달하고, R의 행과 열이 모두 G = RR과T G′ = RRT 둘 다 표준 형태를 가지며 적절히 정규화된 경우, 우리는 글을 쓸 수 있다는 것을 보여주었다.

여기서 W, X, Y, Z는 (n/2)×(n/2)×(n/2) 행렬로 z = -w, y = x, w2+x2 = 2n-2를 만족하는 일정한 행과 열 합이 w, x, y, z이다.따라서 Ehlich-Wojtas 구속은 2n-2가 두 제곱의 합으로 표현되지 않는 한 달성할 수 없다.

Ehlich's bound to n mod 3 (mod 4)

n이 홀수인 경우, 행에 -1을 곱하는 자유를 사용하여 R의 각 행에 짝수 수의 원소 1과 홀수 수의 원소 -1을 포함하는 조건을 부과할 수 있다.이러한 정상화를 가정할 경우 G의 속성 1이 다음과 같이 강화될 수 있음을 알 수 있다.

  1. G는 n(mod 4)에 해당하는 정수 원소를 갖는 행렬이다.

n ≡ 1 (mod 4)에서는 바르바의 최적 형태가 이 더 강한 성질을 만족시키지만, n ≡ 3 (mod 4)에서는 충족되지 않는다.후자의 경우 바운드가 날카로워질 수 있다는 뜻이다.Ehlich[7] 때 n≡ 3(모드 4), 강화된 속성이 어디 제이는 그all-one 매트릭스와 그의 대각선 블록 형태(n-3)I+4J의 B는block-diagonal가 잘 된 G의maximal-determinant 형태 B−J 같이 쓸 수 있습니다. 게다가, 그는으로 월에 나타나 최적의 형태로, 블록, s의 숫자 n에 달려 있었다는 것을 보여 주었다.e아래 표와 각 블록의 크기 r 또는 크기 r+1을 가지고 있는지 여부. 여기서 = / r

n s
3 3
7 5
11 대여섯
15 − 59 6
≥ 63 7

n=11이 두 가지 가능성이 있는 경우를 제외하고, 최적 형태는 행 집합의 최대 곱하기와 그에 상응하는 열 집합의 -1까지가 고유하며 행과 열에 순열을 동시에 적용하는 것이다.이 최적의 형태는 바운드로 이어진다.

여기서 v = n-rs는 r+1 크기의 블록 수입니다. u =s-v는 r 크기의 블록 수입니다.Cohn은[8] 경계를 분석하고 n = 3을 제외하고, 일부 양의 정수 t에 대해서는 n = 112t2±28t+7에 대해서만 정수라고 결정했다.타무라는[9] 2차 형태의 합리적 등가성에 관한 하세-밍코스키 정리를 이용하여 바운드의 달성성에 대한 추가적인 제한을 도출했고, Ehlich의 바운드가 실현 가능한 가장 작은 n > 3은 511임을 보여주었다.

최대 크기 21까지의 최대 결정 요인

다음 표에는 n = 21까지 {1, -1}개의 행렬의 최대 결정 요인이 제시되어 있다.[10]22사이즈는 가장 작은 오픈 케이스다.표에서 D(n)는 최대 결정 인자를 2로n−1 나눈 값이다.마찬가지로 D(n)는 n-1 크기의 {0, 1} 행렬의 최대 결정 인자를 나타낸다.

n D(n) 메모들
1 1 하다마드 행렬
2 1 하다마드 행렬
3 1 엘리히 바운드
4 2 하다마드 행렬
5 3 Barba 바운드 연결, 순환 행렬
6 5 엘리히-우즈타스 바운드
7 9 에를리히 바운드 98.20%
8 32 하다마드 행렬
9 56 바르바 바운드 84.89%
10 144 엘리히-우즈타스 바운드
11 320 Ehlich 바운드 94.49%; 비등가 행렬 3개
12 1458 하다마드 행렬
13 3645 Barba 경계 달성, 최대 결정 행렬은 순서 3의 투영 평면의 발생 행렬 {1,-1}임
14 9477 엘리히-우즈타스 바운드
15 25515 에를리히 바운드 97.07%
16 131072 Hadamard 행렬, 5개의 등가 행렬
17 327680 Barba 바운드 87.04%, 비등가 행렬 3개
18 1114112 Elich-Wojtas 바인딩됨; 비등가 행렬 3개
19 3411968 Ehlich 바운드 97.50% 달성, 비등가 행렬 3개
20 19531250 Hadamard 행렬, 세 개의 등가 행렬
21 56640625 Barba 바운드 90.58%, 비등가 행렬 7개

참조

  1. ^ Hadamard, J. (1893), "Résolution d'une question relative aux déterminants", Bulletin des Sciences Mathématiques, 17: 240–246
  2. ^ Sylvester, J. J. (1867), "Thoughts on inverse orthogonal matrices, simultaneous sign successions, and tessellated pavements in two or more colours, with applications to Newton's rule, ornamental tile-work, and the theory of numbers", London Edinburgh Dublin Phil. Mag. J. Sci., 34 (232): 461–475, doi:10.1080/14786446708639914
  3. ^ Galil, Z.; Kiefer, J. (1980), "D-optimum weighing designs", Ann. Stat., 8 (6): 1293–1306, doi:10.1214/aos/1176345202
  4. ^ Barba, Guido (1933), "Intorno al teorema di Hadamard sui determinanti a valore massimo", Giorn. Mat. Battaglini, 71: 70–86.
  5. ^ Ehlich, Hartmut (1964), "Determinantenabschätzungen für binäre Matrizen", Math. Z., 83: 123–132, doi:10.1007/BF01111249, S2CID 120916607.
  6. ^ Wojtas, M. (1964), "On Hadamard's inequality for the determinants of order non-divisible by 4", Colloq. Math., 12: 73–83, doi:10.4064/cm-12-1-73-83.
  7. ^ Ehlich, Hartmut (1964), "Determinantenabschätzungen für binäre Matrizen mit n ≡ 3 mod 4", Math. Z., 84: 438–447, doi:10.1007/BF01109911, S2CID 116683967.
  8. ^ Cohn, J. H. E. (2000), "Almost D-optimal designs", Utilitas Math., 57: 121–128.
  9. ^ Tamura, Hiroki (2006), "D-optimal designs and group divisible designs", Journal of Combinatorial Designs, 14 (6): 451–462, doi:10.1002/jcd.20103.
  10. ^ Sloane, N. J. A. (ed.). "Sequence A003432 (Hadamard maximal determinant problem: largest determinant of a (real) {0,1}-matrix of order n.)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.