Det är ABSTRACT. Detta dokument fastställer att varje positiv-definit matris kan skrivas som en positiv linjär kombination av yttre produkter av heltal-värderade vektorer vars poster begränsas av det geometriska medelvärdet av tillståndsnummer och dimensionen av matrisen. Detta dokument behandlar en geometrisk fråga som uppstår i teorin om diskret normal approximation [BLX15] och i analysen av hårdvara för genomförande matris multiplikation [LUW15]. Problemet kräver att vi representerar en nonsingular kovariansmatris som en positiv linjär kombination av yttre produkter av heltal vektorer. Den teoretiska utmaningen är att få en optimal gräns på omfattningen av de heltal som krävs som en funktion av tillstånd nummer av matrisen. Vi fastställer följande resultat. Detta resultat har en alternativ tolkning som en matris factorization: I detta uttryck, Z är en d × r heltalsmatris med poster avgränsade av m. R × r matrisen är icke-negativ och diagonal. Beviset för teorem 1.1 finns i avsnitt 3. Avsnitt 4 visar att beroendet av tillståndsnumret inte kan förbättras. Vi anser att beroendet av dimensionen också är optimalt, men vi hittade inget exempel som bekräftar detta antagande. Detta avsnitt innehåller korta preliminärer. Böckerna [HJ90, Bha97, Bar02, BV04] är bra grundreferenser för teknikerna i detta papper. Vi använder små kursiv bokstäver, t.ex. c, för skaläror. Små bokstäver i fetstil, till exempel z, betecknar vektorer. Stora bokstäver med fetstil, som A, hänvisar till matriser. Vi skriver z i för i th komponenten i en vektor z, och en i j för (i, j ) komponenten i en matris A. Den j th kolumnen i matris A kommer att betecknas med en j. Vi arbetar främst i det verkliga linjära utrymmet H d av verkliga d × d symmetriska matriser, utrustade med den vanliga komponentvis addition och skalar multiplikation:
REF visade att varje positiv-definit matris B medger en exakt semidiskret faktorisering (8.2) där V = W och faktorn V har heltalsposter som avgränsas i termer av tillståndsnummer och dimension.
Integer factorization of a positive-definite matrix
{'venue': 'SIAM J. Discrete Math.', 'journal': 'SIAM J. Discrete Math.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}