Skalarprodukt & Permutationen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 15:51 Mo 26.02.2007 | | Autor: | BJJ |
Hallo,
eine Knobelaufgabe, die ich bisher nicht loesen konnte:
Sei V = [mm] \R^n [/mm] ein euklidischer Vektorraum der Dimension n und es sei [mm] \Pi_n [/mm] die Menge aller (n [mm] \times [/mm] n)-Permutationsmatrizen.
Angenommen es seien [mm] x_1, x_2, [/mm] ... [mm] x_k [/mm] linear unabhaengig mit der folgenden Eigenschaften:
1. Die Komponenten der Vektoren [mm] x_1, [/mm] ..., [mm] x_k [/mm] sind nicht-negativ.
2. [mm] \summe_{i=1}^{k} \summe_{j=1}^{k} x_i^T x_j \ge \summe_{i=1}^{k}\summe_{j=1}^{k} (P_i x_i)^T (P_j x_j)
[/mm]
fuer alle Permutationsmatrizen [mm] P_1, [/mm] ..., [mm] P_k \in \Pi_n. [/mm] Man kann das geometrisch wie folgt auffassen: Permutationsmatrizen sind orthogonale Abbildungen, die laengeninvariant sind. Das Skalarprodukt bedeutet geometrisch
x^Ty = ||x|| ||y|| cos [mm] \alpha,
[/mm]
wobei [mm] \alpha [/mm] der Winkel zwischen x und y ist. Das heisst also, dass unsere Vektoren [mm] x_1, x_2, [/mm] ..., [mm] x_k [/mm] durch Permutationen ihrer Komponenten nicht "kompakter" bzw "dichter" gepackt werden koennen. Bsp:
Sei [mm] x_1 [/mm] = (1, 2) und [mm] x_2 [/mm] = (2, 4). Dann haben wir einerseits [mm] x_1^Tx_2 [/mm] = 9. Andererseits gilt
(1, 2)*(4, [mm] 2)^T [/mm] = 8 < 9
(2, 1)*(2, [mm] 4)^T [/mm] = 8 < 9
(2, 1)*(4, [mm] 2)^T [/mm] = 9 [mm] \le [/mm] 9
Insgesant folgt also, dass man [mm] x_1 [/mm] und [mm] x_2 [/mm] durch Permutationen ihrer Komponenten nicht naeher bringen kann.
Sei nun x ein Vektor aus dem von [mm] x_1, [/mm] ..., [mm] x_k [/mm] aufgespannten Unterraum mit den Eigenschaften
1. Die Komponenten von x sind nicht-negativ
2. [mm] (\summe_{i=1}^{k} x_i)^Tx \ge (\summe_{i=1}^{k} x_i)^TPx [/mm]
fuer alle P [mm] \in \Pi_n. [/mm] Geometrisch bedeutet das also, dass man die Vektoren [mm] x_1, x_2, [/mm] ..., [mm] x_k [/mm] und x nicht "dichter" packen kann.
Frage: Sei nun P eine Permutationsmatrix mit
[mm] (\summe_{i=1}^{k} x_i)^Tx [/mm] = [mm] (\summe_{i=1}^{k} x_i)^TPx.
[/mm]
Gilt dann Px = x?
Man koennte x als Linearkombination der [mm] x_1, [/mm] ..., [mm] x_k [/mm] darstellen. Doch wie es dann weitergehen koennte ist mir ein Raetsel.
Vielen Dank und Gruss
bj
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:24 Di 27.02.2007 | | Autor: | BJJ |
Hallo,
um die Frage zu beantworten habe ich folgendes versucht:
Sei x = [mm] a_1 x_1 [/mm] + ... + [mm] a_k x_k,
[/mm]
wobei die Koeffizienten nach Vorraussetzung alle nicht-negativ sind. Nach Annahme ist dann
$ [mm] (\summe_{i=1}^{k} x_i)^Tx [/mm] = [mm] \summe_i \summe_j a_j x_i^T x_j \ge \summe_{i}\summe_j a_j x_i^T Px_j [/mm] $
fuer alle $P [mm] \in \Pi_n$.
[/mm]
Angenommen es gibt ein $Q [mm] \in \Pi_n$ [/mm] mit
1. Qx [mm] \ne [/mm] x
2. [mm] $\summe_i \summe_j a_i x_i^T x_j [/mm] = [mm] \summe_{i}\summe_j a_i Qx_i^T x_j [/mm] $,
wobei ich gegenueber der obigen Ungleichungskette aus aesthetischen Gruenden die Anordnung der Vektoren etwas umgeordnet habe.
Genau hier haenge ich fest. Eine Permutation ist ja eine orthogonale Abbildung. Deswegen haben wir
[mm] $\summe_i \summe_j a_i x_i^T x_j [/mm] = [mm] \summe_{i}\summe_j a_i Qx_i^T x_j [/mm] = [mm] \summe_{i}\summe_j a_i Qx_i^T Qx_j [/mm] $,
Kann man hier eine Aussage darueber machen, das dann entgegen der Annahme Qx = x gelten muss? Zum Beispiel ueber die Diagonalisierung?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:20 Do 29.03.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
