Matrixprodukt von Adjazenzmatrix und ihrer transponierten

07.07.2014, 10:12

Andreaske

Matrixprodukt von Adjazenzmatrix und ihrer transponierten

Hallo an Alle!

Ich mache gerade nebenbei ein Wirtschaftsinformatik-Fern-Studium und muss in einem Kurs Matrizzenprodukte bilden, kenne mich aber sehr wenig damit aus. Könntet Ihr mir vielleicht auf die Sprünge helfen?

Nur zur Erklärung, hier geht es um Authoritywerte (wie gut der Inhalt einer Internetseite auf eine gegebene suchanfrage passt) und Hubwerte (wie oft ein Knoten auf eine oder mehrere Authorities verweist (-> wo man Authority findet)) -> der Zeilenvektor dürfte der Authorityvektor sein, da dies ausgehende Verbindungen sind. Der Spaltenvektor müsste dann der Hubvektor sein, da dies eingehende Verbindungen sind!

Aufgabe:
"Bestimmen Sie die Hub- und Authority-Vektoren h und a für die Knoten des Graphen, indem Sie das nachfolgende Eigenvektor Problem lösen:
$\begin{eqnarray*} A \times A^{T} \times h = m \times h \end{eqnarray*}$
$\begin{eqnarray*} A^{T} \times A \times a = m \times h \end{eqnarray*}$ "

1. Transponieren -> einfach Zeilen und Spalten vertauschen, ist klar
$\begin{eqnarray*} A = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix} , A^T = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix} \end{eqnarray*}$

2. Ich verstehe jedoch nicht, wie man das Matrixprodukt bildet.

In der Lösung steht, dass sich das zu lösende Eigenvektorproblem beschreiben lässt durch:
$\begin{eqnarray*} A \times A^{T} \times \vec{h} = m \times \vec{h} \end{eqnarray*}$
$\begin{eqnarray*} A^{T} \times A \times \vec{a} = m \times \vec{h} \end{eqnarray*}$

mit $\begin{eqnarray*} A \times A^{T} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 1 \\ 0 & 1 & 1 \end{pmatrix} und A^{T} \times A = \begin{pmatrix} 2 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix} \end{eqnarray*}$

Wie kommt man auf diese Werte? Was muss man mit was multiplizieren?

Danke euch!

07.07.2014, 10:17

klarsoweit

Auf diesen Beitrag antworten »

RE: Matrixprodukt von Adjazenzmatrix und ihrer transponierten
zum Thema Matrixmultiplikation: http://de.wikipedia.org/wiki/Matrix_%28M...nmultiplikation

07.07.2014, 10:41

Andreaske

Auf diesen Beitrag antworten »

Hier steht "die Produktsummenformel, [...], auf Paare aus einem Zeilenvektor der ersten und einem Spaltenvektor der zweiten Matrix angewandt wird"

Heißt das, für c1,1 muss ich multiplizieren: a1,1 * b1,1 + a1,2 * b2,1?

07.07.2014, 10:58

RavenOnJ

Auf diesen Beitrag antworten »

Die Formel dazu steht da ja:

$\begin{eqnarray*} c_{ij}=\sum_{k=1}^m a_{ik}\cdot b_{kj} \end{eqnarray*}$

Also bei Multiplikation von $\begin{eqnarray*} 2\times 2 \end{eqnarray*}$ -Matrizen $\begin{eqnarray*} C=A\cdot B \end{eqnarray*}$ beispielsweise $\begin{eqnarray*} c_{11}=a_{11} b_{11}+ a_{12}b_{21} \end{eqnarray*}$ usw..

07.07.2014, 11:09

Andreaske

Auf diesen Beitrag antworten »

Ah ok, ganze Zeile * ganzer Spalte - habe es verstanden, vielen Dank!

Eine weitere Frage hätte ich noch:
Nach der Matrizzenmultiplikation muss man dann den Hubvektor berechnen - dies wird gemacht mit Berechnung charakteristisches Polynom P(m) durch Aufstellen der Eigenwertgleichung A * A^T:
$\begin{eqnarray*} P(m) = det(A \times A^{T} - mE) = \begin{vmatrix} 1-m & 0 & 0 \\ 0 & 2-m & 1 \\ 0 & 1 & 1-m \end{vmatrix} = -m^{3} +4m^{2} -4m +1 \end{eqnarray*}$

und die Eigenwerte durch Lösen der Gleichung P(m)=0 bestimmt. Hier ergeben sich 3 reelle Werte:
$\begin{eqnarray*} m_{1} = 0,38, m_{2} = 1, m_{3} = 2,62 \end{eqnarray*}$ (statt ist-gleich = sollte hier zirka-gleich ~~)

Das mit "-m" bzw. "-lambda" habe ich bereits nachgelesen und verstehe ich. Ich verstehe jedoch nicht, wie man daraus diese Gleichung mit -m^3 etc. ableitet. Und wie man dann auf die reellen Zahlen kommt. Könntet Ihr mir hier auch auf die Sprünge helfen?

Danke!

[edit]
Könnte es sein, dass ich das hier finde?
http://de.wikipedia.org/wiki/Skalarmultiplikation

07.07.2014, 11:14

klarsoweit

Auf diesen Beitrag antworten »

Die "senkrechten" Striche um die Matrix bedeuten "Determinante". Und wie du selber sagst, sind die Eigenwerte Lösungen der Gleichung P(m)=0. Wie man die Nullstellen eines Polynoms bestimmt, sollte an dieser Stelle eigentlich bekannt sein.

07.07.2014, 20:38

Andreaske

Auf diesen Beitrag antworten »

Verstehe alles bis dahin! Vielen Dank!

Eine weitere Frage Augenzwinkern

bei der Polynomdivision bekommt man 3 reelle Lösungen
m1 = 0,38
m2 = 1
m3 = 2,62

Nun soll man mit dem beitragsmäßig größtem Eigenwert (-> m3 = 2,62) den Hubvektor h und den Authorityvektor a bestimmen (wie bereits angemerkt ist Hubvektor=Zeilenvektor (ausgehende Verbindungen) und der Authorityvektor=Spaltenvektor (eingehende Verbindungen)).

Das urspr. Eigenvektorproblem war ja $\begin{eqnarray*} A \times A^{T} \times h = m \times h \end{eqnarray*}$

Heißt das, ich nehme die Determinante $\begin{eqnarray*} det(A \times A^{T} - mE) \end{eqnarray*}$ mit dem beitragsmäßig größtem Eigenwert ( $\begin{eqnarray*} m_{3} \end{eqnarray*}$ ) mal dem Hubvektor
-> $\begin{eqnarray*} (A \times A^{T} - m_{3}E) \times \vec{h} \end{eqnarray*}$ ?

Falls dies korrekt ist, könnt ihr mir weiterhelfen, wie ich das ausrechne? $\begin{eqnarray*} \vec{h} \end{eqnarray*}$ ist ja der Hubvektor, also der Zeilenvektor, richtig?
Wie rechne ich $\begin{eqnarray*} (A \times A^{T} - m_{3}E) \end{eqnarray*}$ aus?
Wenn ihr mir zeigen könntet wo ich suchen kann (zB wikipedia link) oder helfen könntet...? Ist das vielleicht das Skalarprodukt?

Thx!

08.07.2014, 09:16

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von Andreaske
Heißt das, ich nehme die Determinante $\begin{eqnarray*} det(A \times A^{T} - mE) \end{eqnarray*}$ mit dem beitragsmäßig größtem Eigenwert ( $\begin{eqnarray*} m_{3} \end{eqnarray*}$ ) mal dem Hubvektor
-> $\begin{eqnarray*} (A \times A^{T} - m_{3}E) \times \vec{h} \end{eqnarray*}$ ?

Die Determinante brauchtest du nur für die Bestimmung des charakteristisches Polynoms. Was jetzt ansteht, ist die Lösung der Gleichung $\begin{eqnarray*} (A \cdot A^T - m_3 E) \cdot \vec{h} = 0 \end{eqnarray*}$ .
Anders gesagt: du brauchst den Kern der Matrix $\begin{eqnarray*} A \cdot A^T - m_3 E \end{eqnarray*}$ .

Im Zweifelsfall würde ich für m3 auch eher die exakte Darstellung $\begin{eqnarray*} m_3 = \frac{3+ \sqrt 5}{2} \end{eqnarray*}$ bevorzugen. smile

09.07.2014, 19:05

Andreaske

Auf diesen Beitrag antworten »

Tut mir leid aber deine Antwort sagt mir leider gar nichts!

Hab mir ein paar Videos zum Berechnen eines Matrixkerns angesehen. Geht das in die richtige Richtung?
$\begin{eqnarray*} ( A \times A^{T} -m_{3}E ) = \begin{pmatrix} 1-2,62 & 0 & 0 \\ 0 & 2-2,62 & 1 \\ 0 & 1 & 1-2,62 \end{pmatrix} * \begin{pmatrix} h_{1} \\ h_{2} \\ h_{3} \end{pmatrix} = \begin{pmatrix} -1,62 & 0 & 0 \\ 0 & -0,62 & 1 \\ 0 & 1 & -1,62 \end{pmatrix} * \begin{pmatrix} h_{1} \\ h_{2} \\ h_{3} \end{pmatrix} \end{eqnarray*}$

->
$\begin{eqnarray*} -1,62h_{1} = 0 \end{eqnarray*}$ -> $\begin{eqnarray*} h=0 \end{eqnarray*}$ ?

$\begin{eqnarray*} -0,62h_{2} + 1h_{3} = 0 ?? \end{eqnarray*}$

10.07.2014, 09:27

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von Andreaske
Tut mir leid aber deine Antwort sagt mir leider gar nichts!

Wäre ja nett, wenn du verrätst, was du nicht verstehst. Ich gehe natürlich davon aus, daß dir Begriffe wie Kern oder Gauß-Algorithmus zum Lösen eines linearen Gleichungssystems bekannt sind.

Zitat:

Original von Andreaske
$\begin{eqnarray*} -1,62h_{1} = 0 \end{eqnarray*}$ -> $\begin{eqnarray*} h=0 \end{eqnarray*}$ ?

Du meinst: h_1 = 0

Zitat:

Original von Andreaske
$\begin{eqnarray*} -0,62h_{2} + 1h_{3} = 0 ?? \end{eqnarray*}$

Hier zeigt sich jetzt die Schwäche, daß du einen gerundeten Eigenwert nimmst. Normalerweise müßtest du das $\begin{eqnarray*} \frac{1}{0,62} \end{eqnarray*}$ -fache der 2. Zeile zur 3. Zeile addieren können, so daß dort eine Nullzeile entsteht. Mit einem gerundeten Eigenwert funktioniert das natürlich nicht.

18.07.2014, 16:32

Andreaske

Auf diesen Beitrag antworten »

Hallo!

Zitat:

Wäre ja nett, wenn du verrätst, was du nicht verstehst. Ich gehe natürlich davon aus, daß dir Begriffe wie Kern oder Gauß-Algorithmus zum Lösen eines linearen Gleichungssystems bekannt sind.

Leider darfst du davon nicht ausgehen! Um vielleicht kurz meinen Hintergrund zu erklären:
Ich habe nach der 4. Klasse Gymnasium eine Handelsakademie (5 Jahre) gemacht - also mehr Betr.wirtsch., Buchhaltung/Rechnungswesen, Ökonomie und wengier höhere Mathematik.

Dann habe ich einen Master in Finanzen gemacht und mache jz neben der Arbeit eben das Fernstudium Wirtsch.informatik - bei diesem muss ich 1 Fach aus der Informatik wählen und genau bei diesem habe ich jetzt Probleme (der Rest geht einwandfrei - das sind hptsl Informationsmanagement Fächer).

Wenn du sagst, der Gauß-Algorithmus hilft mir bei diesem Problem schau ich mir gern ein paar Videos auf youtube an / lese drüber und versuche selbst draufzukommen. Jedoch brauche ich die Stichworte - genau diese fehlen mir!! =/

21.07.2014, 08:56

klarsoweit

Auf diesen Beitrag antworten »

Da haben wir Helfern natürlich schon ein Problem, denn wir gehen durchaus davon aus, daß gewisse Begriffe bekannt sind. Es ist auch nicht verständlich, warum bei einem Studiengang nicht klar beschrieben wird, welche Voraussetzungen man mitbringen muß. Nun gut.

Zitat:

Original von Andreaske
Wenn du sagst, der Gauß-Algorithmus hilft mir bei diesem Problem schau ich mir gern ein paar Videos auf youtube an / lese drüber und versuche selbst draufzukommen. Jedoch brauche ich die Stichworte - genau diese fehlen mir!! =/

Am besten postest du nochmal den Schritt, wo es im Moment klemmt, dann versuche ich das ausführlicher zu erklären.

Neue Frage »

Antworten »

Matrixprodukt von Adjazenzmatrix und ihrer transponierten

Verwandte Themen