Wie kann ich von zwei oder mehr Vek­to­ren Linear­kom­bi­na­tio­nen er­stel­len, so daß mög­lichst viele Kom­po­nen­ten Null sind?

Ich habe m Vek­to­ren in einem Vek­tor­raum ℚⁿ (m≪n), deren Ko­or­di­na­ten mir be­kannt sind (sie kön­nen als ganz­zah­lig an­ge­nom­men wer­den). Diese Vek­to­ren kom­men aus einer Be­rech­nung eines Eigen­systems zu einem ent­arte­ten Eigen­wert und span­nen einen Un­ter­raum auf, und ich suche nun eine Mög­lich­keit, eine Ba­sis für die­sen Unter­raum zu fin­den, in dem mög­lichst viele Ko­or­di­na­ten der Ba­sis­vek­to­ren Null sind, und der Rest wenn mög­lich po­si­tiv. Ortho­go­na­li­tät ist da­bei kein Thema.

Beispiel: Ich habe a=(1,3,1) und b=(1,0,−2). Als Lö­sung sollte mir der Al­go­rith­mus die Vek­to­ren ⅓(a−b)=(0,1,1) und ⅓(2a+b)=(1,2,0) vor­schla­gen. Ich habe da­bei die Ver­mu­tung, daß eine sol­che Lö­sung mit aus­schließ­lich nicht­nega­ti­ven Ko­ordi­na­ten für mei­ne An­wen­dung im­mer existiert, bin mir aber nicht sicher.

Ist eine solche diffuse Aufgabenstellung überhaupt klar for­mu­lier­bar, und wenn ja, gibt es einen Al­go­rith­mus, der die Lösung findet?

Answer 1

[erpis]

Ich habe da­bei die Ver­mu­tung, daß eine sol­che Lö­sung mit aus­schließ­lich nicht­nega­ti­ven Ko­ordi­na­ten für mei­ne An­wen­dung im­mer existiert, bin mir aber nicht sicher.

Ja, das sollte stimmen

Answer 2

[pbbb5885]

Hallo, besser spät als nie!

Vielleicht hilft es ja. Je nach dem wo du das darstellen möchtest? Und ob überhaupt noch.

1. Gegeben: \( A \in \mathbb{Q}^{n \times m} \) mit Spalten \( a_1, \dots, a_m \). 

2. Variablen:

  \( x \in \mathbb{Q}^m \) — Linearkombinationskoeffizienten, 

  \( v = A x \in \mathbb{Q}^n \) — resultierender Vektor, 

  \( z \in \{0,1\}^n \) — Indikatorvariablen für \( v_i \ne 0 \). 

3. Nebenbedingungen (für jedes \( i = 1,\dots,n \))

  \[

  -M z_i \le v_i \le M z_i

  \] 

  (z. B. \( M = 10^3 \)) 

  und ggf

  \[

  v_i \ge 0 \quad \text{(für nichtnegative Koordinaten)}

  \] 

4. Zielfunktion:

  \[

  \min \sum_{i=1}^n z_i

  \] 

5. Wiederhole für mehrere \( x^{(k)} \), sodass \( v^{(1)}, \dots, v^{(k)} \) linear unabhängig sind. 

  Prüfe dabei z. B. Rang \( \text{rank}(V) = k \) mit \( V = [v^{(1)} \dots v^{(k)}] \).

Das kannst du direkt in einem ILP-Solver darstellen.

Liebe Grüße