Matroids Matheplanet Forum Index
Moderiert von Fabi Dune ligning
Lineare Algebra » Matrizenrechnung » Rang einer Null-Eins-Matrix mit höchstens 3 Spalten
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Rang einer Null-Eins-Matrix mit höchstens 3 Spalten
LordWedel
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 14.06.2018
Mitteilungen: 7
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-04-08


Hallo ich habe in einem Aufsatz aus der Spieltheorie folgendes Lemma gefunden und würde gerne verstehen, wie man dieses beweisen könnte.

"Sei A eine $m \times n$ Matrix  bestehnd nur aus Einsen und Nullen. Und $n$ (die Anzahl der Spalten) sei nicht größer als 3. Wenn es zu einem Paar unterschiedlicher Spalten $j$ und $\hat{j}$ (im englischen Original distinct columns) eine Zeile $i$ von A gibt, deren $j$-ter Eintrag 1 und deren $\hat{j}$-ter Eintrag 0 ist, dann hat die Matrix den Rang $n$." (vgl. Lemma 4 in "The partnered core of a game with side payments" von Reny, Winter & Wooders)

Klar ist, dass dieses Lemma im Fall $n=1$ falsch formuliert ist.

Als Beweis wird nur angegeben, dass es 8 mögliche verschiedene Zeilen und, dass es straightforward sei alle Möglichkeiten durchzuprobieren.

Auch würde ich gerne wissen, was ich genau unter verschiedener Zeile zu verstehen habe: Ist damit gemeint, dass jedes Element verschieden ist oder nur, dass sie nicht identisch sind?

Weil z.B. für $A= \left( \begin{matrix}
1 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 0 & 1
\end{matrix} \right)$ sind die erste und die zweite Spalte verschieden und der zweiten Reihe ist der erste Eintrag 1 und der zweite 0, aber der Rang dieser Matrix $A$ ist nur 2.



  Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 3077
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-04-08


Hallo und Willkommen auf dem Matheplaneten!

Könntest du das Lemma im Originalwortlaut zitieren? row heißt beispielsweise Zeile und nicht Spalte.


-----------------
⊗ ⊗ ⊗



  Profil  Quote  Link auf diesen Beitrag Link
LordWedel
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 14.06.2018
Mitteilungen: 7
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-04-08


Ja natürlich, das Lemma ist im Original das folgende:

"Suppose that $A$ is an $m \times n$ matrix consisting entirely of zeros and ones and that $n$, the number of columns, is no greater than three. If for any pair of distinct columns, $j$ and $\hat{j}$ there is a row, $i$, of A whose $j$-th entry is one and whose $\hat{j}$-th entry is zero, then $A$ has rank $n$.

Proof: Since there are potentially eight distinct rows, it is straightforward to simply exhaust all possibilities."

Ich wäre auch schon sehr dankbar, wenn jemand eine Idee hätte, wo ich dieses Lemma in der Literatur verifiziert bekomme.



  Profil  Quote  Link auf diesen Beitrag Link
Diophant
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.01.2019
Mitteilungen: 3805
Aus: Rosenfeld, BW
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-04-08

\(\begingroup\)\(\newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}} \newcommand{\on}{\operatorname}\)
Hallo,

eine Beweisidee habe ich gerade noch nicht, aber das hier scheint mir einfach erklärbar zu sein:

2020-04-08 10:39 - LordWedel im Themenstart schreibt:
Als Beweis wird nur angegeben, dass es 8 mögliche verschiedene Zeilen und, dass es straightforward sei alle Möglichkeiten durchzuprobieren.

Auch würde ich gerne wissen, was ich genau unter verschiedener Zeile zu verstehen habe: Ist damit gemeint, dass jedes Element verschieden ist oder nur, dass sie nicht identisch sind?

Es gibt \(2^3=8\) Möglichkeiten, einen Zeilenvektor der Dimension 3 auf unterschiedliche Arten mit Nullen und Einsen zu belegen (-> Variationen mit Wiederholung). Und diese 8 Möglichkeiten dürften hier gemeint sein.


Gruß, Diophant
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 3077
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-04-08


Ich übersetze mal, wie ich es verstehe:

Sei $A$ eine $m\times n$-Matrix, deren Einträge ausschließlich $0$ oder $1$ sind, und die höchstens $3$ Spalten hat. Falls es zu jedem Paar verschiedener Spalten(-indizes) $j$, $j'$, eine Zeile $i$ gibt, so dass $a_{ij} = 1$ und $a_{ij'} = 0$, dann hat $A$ den Rang $n$.

Zuerst dachte ich, das sei eine komplizierte Art auszudrücken, dass die Spalten sich paarweise unterscheiden, aber es ist mehr, es schließt z.B. den Fall einer ganzen $1$-Spalte aus.

In deinem Beispiel gibt es für $j=2$, $j'=1$ bspw. keine Zeile $i$ mit $a_{ij}=1$ und $a_{ij'}=0$.

[Die Antwort wurde nach Beitrag No.2 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
LordWedel
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 14.06.2018
Mitteilungen: 7
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2020-04-08


2020-04-08 11:08 - ligning in Beitrag No. 4 schreibt:
Ich übersetze mal, wie ich es verstehe:

Sei $A$ eine $m\times n$-Matrix, deren Einträge ausschließlich $0$ oder $1$ sind, und die höchstens $3$ Spalten hat. Falls es zu jedem Paar verschiedener Spalten(-indizes) $j$, $j'$, eine Zeile $i$ gibt, so dass $a_{ij} = 1$ und $a_{ij'} = 0$, dann hat $A$ den Rang $n$.

Zuerst dachte ich, das sei eine komplizierte Art auszudrücken, dass die Spalten sich paarweise unterscheiden, aber es ist mehr, es schließt z.B. den Fall einer ganzen $1$-Spalte aus.

In deinem Beispiel gibt es für $j=2$, $j'=1$ bspw. keine Zeile $i$ mit $a_{ij}=1$ und $a_{ij'}=0$.

[Die Antwort wurde nach Beitrag No.2 begonnen.]

Ja genau, aber wenn ich dieses Lemma richtig verstehe muss es nur ein solches Paar geben und nicht für alle möglichen Paare gelten, oder seht ihr das anders?



  Profil  Quote  Link auf diesen Beitrag Link
LordWedel
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 14.06.2018
Mitteilungen: 7
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2020-04-08

\(\begingroup\)\(\newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}} \newcommand{\on}{\operatorname} \newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}} \newcommand{\on}{\operatorname}\)
2020-04-08 11:07 - Diophant in Beitrag No. 3 schreibt:
Hallo,

eine Beweisidee habe ich gerade noch nicht, aber das hier scheint mir einfach erklärbar zu sein:

2020-04-08 10:39 - LordWedel im Themenstart schreibt:
Als Beweis wird nur angegeben, dass es 8 mögliche verschiedene Zeilen und, dass es straightforward sei alle Möglichkeiten durchzuprobieren.

Auch würde ich gerne wissen, was ich genau unter verschiedener Zeile zu verstehen habe: Ist damit gemeint, dass jedes Element verschieden ist oder nur, dass sie nicht identisch sind?

Es gibt \(2^3=8\) Möglichkeiten, einen Zeilenvektor der Dimension 3 auf unterschiedliche Arten mit Nullen und Einsen zu belegen (-> Variationen mit Wiederholung). Und diese 8 Möglichkeiten dürften hier gemeint sein.


Gruß, Diophant

Dass es somit 8 Fälle nür $n=3$ gibt, ist mir klar, nur was ist mit den Fällen $n=2$  und $n=1$ (auch wenn man für diesen das Lemma noch umformulieren muss)? Für $n=2$ hätte ich ja nochmal 4 Fälle und für $n=1$ zwei weitere.
Müsste ich diese nicht auch betrachten?
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 3077
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2020-04-08


2020-04-08 11:15 - LordWedel in Beitrag No. 5 schreibt:
Ja genau, aber wenn ich dieses Lemma richtig verstehe muss es nur ein solches Paar geben und nicht für alle möglichen Paare gelten, oder seht ihr das anders?
Es muss für alle Paare gelten: "for any pair" steht da. Wenn es nur eins geben müsste, würde da "for some" stehen.


[Verschoben aus Forum 'Lineare Algebra' in Forum 'Matrizenrechnung' von ligning]



  Profil  Quote  Link auf diesen Beitrag Link
philippw
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.06.2005
Mitteilungen: 1124
Aus: Hoyerswerda
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2020-04-08


2020-04-08 11:15 - LordWedel in Beitrag No. 5 schreibt:
Ja genau, aber wenn ich dieses Lemma richtig verstehe muss es nur ein solches Paar geben und nicht für alle möglichen Paare gelten, oder seht ihr das anders?

"For any pair" bedeuted hier "für jedes Paar", im Sinne von "For any pair, that can be chosen, no matter which one you choose, this always holds.". Wie dein Beispiel zeigt, stimmt die Aussage sonst nicht. Wenn es nur für irgend ein Paar gelten sollte, könnte man etwa "For some pair..." schreiben.

[Die Antwort wurde nach Beitrag No.6 begonnen.]


-----------------
"Eine Wissenschaft ist erst dann als voll entwickelt anzusehen, wenn sie dahin gelangt ist, sich der Mathematik bedienen zu können."
Karl Marx



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2024
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2020-04-08

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}}\)
Hallo,

man könnte es recht kurz so beweisen:
$n=1$ bzw. $n=2$ sind klar, also betrachte $n=3$.
Dann hat $A$ Zeilen der folgenden Form: $(1,a,0), (0,1,b), (0,c,1), (d,0,1)$ mit unbekannten $a,b,c,d\in\{0,1\}$.

Falls $b=0$, dann sind $(1,a,0), (0,1,b), (0,c,1)$ linear unabhängige Zeilen, also hat $A$ Rang 3.

Falls $b=1$, dann sind $(1,a,0), (0,1,b), (d,0,1)$ linear unabhängig, denn $\begin{pmatrix}1&a&0\\ 0&1&1\\d&0&1\end{pmatrix}$ hat Determinante $1+ad \geq 1$.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 3077
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2020-04-08


Für n=1 ist es falsch, denn dann gibt es kein Paar verschiedener Spaltenindizes, so dass die Bedingung trivialerweise erfüllt ist, aber die Matrix kann auch die Nullmatrix, mit Rang 0, sein.




  Profil  Quote  Link auf diesen Beitrag Link
LordWedel
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 14.06.2018
Mitteilungen: 7
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, vom Themenstarter, eingetragen 2020-04-08


Ich wurde freundlicherweise von euch darauf hingewiesen, dass es für alle Paare gelten muss.
Wenn ich dann jetzt diese 8 Fälle betrachten möchte, kann ich dann einfach zeigen, dass beispielsweise für die Zeile: $\color{red}{\left(\begin{matrix} 1& 0 & 0 \end{matrix} \right)}$ es folgende Matrix gibt, die die Vss des Lemmas erfüllen:

$$A=\left(\begin{matrix}
\color{red}1&  \color{red} 0 &\color{red}  0  \\
1 & 0 & * \\
1 & * & 0 \\
0 & 1 & * \\
* & 1 & 0 \\
0 & * & 1 \\
* & 0 & 1
\end{matrix} \right)
= \left\{\begin{matrix}
\text{Gewählte Zeile}\\
j=1 & j'=2\\
j=1 & j'=3\\
j=2 & j'=1\\
j=2 & j'=3\\
j=3 & j'=1\\
j=3 & j'=2
\end{matrix}\right.$$ Dabei wäre $* \in \{0,1\}$ beliebig. Dann würde man ja sehen, dass egal welchen der beiden möglichen Werte $*$ in der entsprechenden Zeile annimmt, dass die Matrix gerade den Rang 3 hat. Da Zeilenvertauschungen ja keinen Einfluss auf den Rang einer Matrix haben, decke ich doch mit diesem "Beispiel" dann alle Fälle ab, für die Zeile $\color{red}{\left(\begin{matrix} 1& 0 & 0 \end{matrix} \right)}$, richtig?

[Die Antwort wurde nach Beitrag No.8 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
LordWedel
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 14.06.2018
Mitteilungen: 7
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, vom Themenstarter, eingetragen 2020-04-08

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}}\)
2020-04-08 12:21 - Nuramon in Beitrag No. 9 schreibt:
Hallo,

man könnte es recht kurz so beweisen:
$n=1$ bzw. $n=2$ sind klar, also betrachte $n=3$.
Dann hat $A$ Zeilen der folgenden Form: $(1,a,0), (0,1,b), (0,c,1), (d,0,1)$ mit unbekannten $a,b,c,d\in\{0,1\}$.

Falls $b=0$, dann sind $(1,a,0), (0,1,b), (0,c,1)$ linear unabhängige Zeilen, also hat $A$ Rang 3.

Falls $b=1$, dann sind $(1,a,0), (0,1,b), (d,0,1)$ linear unabhängig, denn $\begin{pmatrix}1&a&0\\ 0&1&1\\d&0&1\end{pmatrix}$ hat Determinante $1+ad \geq 1$.


Aber erfüllt diese Matrix die Vss., dass es zu jedem Paar $(j,j')$ eine Zeile $i$ mit $a_{ij}=1$ und $a_{ij'}=0$ gibt?
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2024
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2020-04-08

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}}\)

Aber erfüllt diese Matrix die Vss., dass es zu jedem Paar $(j,j')$ eine Zeile $i$ mit $a_{ij}=1$ und $a_{ij'}=0$ gibt?
Das ist nicht die ganze Matrix, sondern nur drei Zeilen der Matrix. Es reicht aus diese drei Zeilen zu betrachten um den Rang zu bestimmen.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
LordWedel
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 14.06.2018
Mitteilungen: 7
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, vom Themenstarter, eingetragen 2020-04-08

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}}\)
2020-04-08 12:35 - Nuramon in Beitrag No. 13 schreibt:

Aber erfüllt diese Matrix die Vss., dass es zu jedem Paar $(j,j')$ eine Zeile $i$ mit $a_{ij}=1$ und $a_{ij'}=0$ gibt?
Das ist nicht die ganze Matrix, sondern nur drei Zeilen der Matrix. Es reicht aus diese drei Zeilen zu betrachten um den Rang zu bestimmen.

Ah ok, cool also noch eine weitere Verallgemeinerung von meinem Versuch?
Aber dann verstehe ich, warum der Beweis vollständig ist und die Aussage zeigt.

Dankeschön!
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2024
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2020-04-08

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}}\)
Meine Fallunterscheidung war sogar unnötig:
Die Zeilen $(1,a,0), (0,1,b), (c,0,1)$ sind immer linear unabhängig, egal welche Werte $a,b,c\in\{0,1\}$ annehmen (die Determinante von $\begin{pmatrix}1&a&0\\ 0&1&b\\c&0&1\end{pmatrix}$ ist $1+abc\not=0$). (Dieser Beweis zeigt auch, dass die Aussage in Charakteristik 2 falsch ist: wähle $a=b=c=1$.).
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
LordWedel hat die Antworten auf ihre/seine Frage gesehen.
LordWedel hatte hier bereits selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]