선형 시스템 모드 2에 대한 솔루션의 존재

Dec 09 2020

허락하다 $A$ (스큐) 대칭 행렬 $\mathbb{Z}/2$. (사실 나는$A$ 방향이 지정된 프레임 링크의 연결 행렬로 $S^3$또는 닫힌 매끄러운 4- 다양체의 교차 형태를 나타내는 행렬. 그러나 다음 진술은 일반적으로 유지되는 것 같습니다.) 나는 다음 선형 시스템에 관심이 있습니다.$\mathbb{Z}/2$, $$a_{i1}x_1+a_{i2}x_2\cdots+a_{in}x_n=a_{ii},\quad i=1,\cdots,n.$$

이 시스템은 항상 해결책이있는 것으로 알려져 있습니다. (참조 : Saveliev의 3- 매니 폴드 토폴로지에 대한 강의 .) 그러나 나는 이것이 사실이 아니라면 왜 사실인지 알 수 없다.$A$ 이상하다 $\mathbb{Z}/2$. 이러한 종류의 선형 시스템을 다루는 일반적인 방법이 있습니까?

답변

1 JyrkiLahtonen Dec 10 2020 at 04:21

이것은 사실이지만 약간 까다 롭습니다. 아이디어는 단순히 행렬을 형식으로 작성하는 것입니다.$$ A=BB^T $$ 그런 식으로 열 공간 $B$ 그것과 같다 $A$. 모든 열$A$ 열의 선형 조합입니다. $B$, 그러나 역 포함을 달성하는 방법이 명확하지 않습니다 (모든 선택에 대해 분명한 것은 아닙니다. $B$).

따라서 현재로서는 완전히 독립적 인 증명을 작성할 수 없습니다. 두 개의 기사를 참조해야합니다.

A. Lempel, 행렬 분해$GF(2)$ 및 트레이스 직교베이스 $GF(2^m)$, SIAM J. Comput., vol. 4, pp. 175-186, 1975 년 6 월.
G. Seroussi, A. Lempel, 특정 Reed-Muller 코드의 최대 가능성 디코딩 , 정보 이론에 대한 IEEE 트랜잭션, Vol. IT-29, 아니. 1983 년 5 월 3 일.

IIRC는 첫 번째 만 필요합니다. 나는 그것을 읽음으로써 전자를 발견했기 때문에 후자를 포함합니다.

Lempel (Lempel-Ziv 명성의)이 첫 번째 기사에서 해결하는 문제는 다음과 같습니다. 그는 주어진 대칭을 쓰고 싶어$n\times n$ 매트릭스 $A$ 위에 $\Bbb{Z}_2$ ~의 형태의 $A=BB^T$최대한 효율적으로. 즉, 그는 열 수를 최소화하고자합니다.$m$ 의 $B$. 그의 대답은

일반적으로 $m$ 순위와 같다 $r(A)$ 의 $A$. 예외는 대각선이$A$ 모두 0입니다. $m=1+r(A)$ 우리가 할 수있는 최선입니다.

Lempel의 결과를 적용하여이 질문을 다음과 같이 해결할 수 있습니다.

대각선의 경우 $A$모두 0이고 주장은 사소합니다. 우리는 사용할 수 있습니다$x_i=0$ 모든 $i$.
그렇지 않은 경우 열 수 $B$ 순위와 같다 $A$. 같이$A=BB^T$ 열 공간 $A$ 다음과 같습니다 $B$.
따라서 대각선이 $A$ 열 공간에 포함되어 있습니다. $B$.
방정식 $A=BB^T$ 의미 $a_{ii}$ 내적과 동일 $(B_i,B_i)$ 의 $i$일행 $B_i$ 의 $B$ 그 자체로.
그러나 $B_i$ 바이너리이므로 $(B_i,B_i)$ 단순히 항목의 합계입니다. $i$다음 행으로 $x^2=x$ 모든 $x\in\Bbb{Z}_2$.
따라서 대각선 $A$ 열의 합계입니다. $B$.
따라서 대각선 $A$ 또한 열 공간에 $A$ 그리고 우리는 끝났습니다.

이것은 불필요하게 엉성하게 느껴집니다. 사용의 아이디어$A=BB^T$직관적으로 나에게 왔습니다. 몇 가지 예를 계산 한 결과$B$합계는 대각선입니다. 전구 시간!