Perron Frobenius Theorem modified
$begingroup$
On this site I found a modified version of Perron Frobenius Theorem
Perron-Frobenius Theorem: If M is a positive, column stochastic matrix, then:
1 is an eigenvalue of multiplicity one.
1 is the largest eigenvalue: all the other eigenvalues have absolute value smaller than 1.
the eigenvectors corresponding to the eigenvalue 1 have either only positive entries or only negative entries. In particular, for the eigenvalue 1 there exists a unique eigenvector with the sum of its entries equal to 1.
In this same site, in Disconnected components section there is a matrix
$$
begin{matrix}
0 & 1 & 0 & 0 & 0 \
1 & 0 & 0 & 0 & 0 \
0 & 0 & 0 & 1/2 & 1/2 \
0 & 0 & 1/2 & 0 & 1/2 \
0 & 0 & 1/2 & 1/2 & 0 \
end{matrix}
$$
This matrix satisfies the conditions therefore for the eigenvalue 1 there exists a unique eigenvector with the sum of its entries equal to 1.
but at least exists two vectors
$u = (1/2,1/2,0,0,0)$
$v = (0,0,1/3,1/3,1/3)$
what happened?
Is modified theorem incorrect?
Thank you!
linear-algebra eigenvalues-eigenvectors page-rank
asked Nov 27 '18 at 4:49
JoseJose
31
$endgroup$
add a comment |
$begingroup$
On this site I found a modified version of Perron Frobenius Theorem
Perron-Frobenius Theorem: If M is a positive, column stochastic matrix, then:
1 is an eigenvalue of multiplicity one.
1 is the largest eigenvalue: all the other eigenvalues have absolute value smaller than 1.
the eigenvectors corresponding to the eigenvalue 1 have either only positive entries or only negative entries. In particular, for the eigenvalue 1 there exists a unique eigenvector with the sum of its entries equal to 1.
In this same site, in Disconnected components section there is a matrix
$$
begin{matrix}
0 & 1 & 0 & 0 & 0 \
1 & 0 & 0 & 0 & 0 \
0 & 0 & 0 & 1/2 & 1/2 \
0 & 0 & 1/2 & 0 & 1/2 \
0 & 0 & 1/2 & 1/2 & 0 \
end{matrix}
$$
This matrix satisfies the conditions therefore for the eigenvalue 1 there exists a unique eigenvector with the sum of its entries equal to 1.
but at least exists two vectors
$u = (1/2,1/2,0,0,0)$
$v = (0,0,1/3,1/3,1/3)$
what happened?
Is modified theorem incorrect?
Thank you!
linear-algebra eigenvalues-eigenvectors page-rank
asked Nov 27 '18 at 4:49
JoseJose
31
$endgroup$
add a comment |
$begingroup$
On this site I found a modified version of Perron Frobenius Theorem
Perron-Frobenius Theorem: If M is a positive, column stochastic matrix, then:
1 is an eigenvalue of multiplicity one.
1 is the largest eigenvalue: all the other eigenvalues have absolute value smaller than 1.
the eigenvectors corresponding to the eigenvalue 1 have either only positive entries or only negative entries. In particular, for the eigenvalue 1 there exists a unique eigenvector with the sum of its entries equal to 1.
In this same site, in Disconnected components section there is a matrix
$$
begin{matrix}
0 & 1 & 0 & 0 & 0 \
1 & 0 & 0 & 0 & 0 \
0 & 0 & 0 & 1/2 & 1/2 \
0 & 0 & 1/2 & 0 & 1/2 \
0 & 0 & 1/2 & 1/2 & 0 \
end{matrix}
$$
This matrix satisfies the conditions therefore for the eigenvalue 1 there exists a unique eigenvector with the sum of its entries equal to 1.
but at least exists two vectors
$u = (1/2,1/2,0,0,0)$
$v = (0,0,1/3,1/3,1/3)$
what happened?
Is modified theorem incorrect?
Thank you!
linear-algebra eigenvalues-eigenvectors page-rank
asked Nov 27 '18 at 4:49
JoseJose
31
$endgroup$
On this site I found a modified version of Perron Frobenius Theorem
Perron-Frobenius Theorem: If M is a positive, column stochastic matrix, then:
1 is an eigenvalue of multiplicity one.
1 is the largest eigenvalue: all the other eigenvalues have absolute value smaller than 1.
the eigenvectors corresponding to the eigenvalue 1 have either only positive entries or only negative entries. In particular, for the eigenvalue 1 there exists a unique eigenvector with the sum of its entries equal to 1.
In this same site, in Disconnected components section there is a matrix
$$
begin{matrix}
0 & 1 & 0 & 0 & 0 \
1 & 0 & 0 & 0 & 0 \
0 & 0 & 0 & 1/2 & 1/2 \
0 & 0 & 1/2 & 0 & 1/2 \
0 & 0 & 1/2 & 1/2 & 0 \
end{matrix}
$$
This matrix satisfies the conditions therefore for the eigenvalue 1 there exists a unique eigenvector with the sum of its entries equal to 1.
but at least exists two vectors
$u = (1/2,1/2,0,0,0)$
$v = (0,0,1/3,1/3,1/3)$
what happened?
Is modified theorem incorrect?
Thank you!
linear-algebra eigenvalues-eigenvectors page-rank
linear-algebra eigenvalues-eigenvectors page-rank
asked Nov 27 '18 at 4:49
JoseJose
31
asked Nov 27 '18 at 4:49
JoseJose
31
asked Nov 27 '18 at 4:49
JoseJose
31
asked Nov 27 '18 at 4:49
JoseJose
31
asked Nov 27 '18 at 4:49
JoseJose
31
31
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The $5times5$ matrix is not positive. It has zero entries.
Remark. And that was probably the reason why Brin et al. introduced the so-called damping factor in their PageRank paper. Without the damping factor, their matrix is merely nonnegative and it might not possess a unique nonnegative eigenvector, i.e. the ranking is not unique. However, by introducing the damping factor (i.e. by considering a convex combination of their matrix with an all-one matrix), the matrix becomes positive and there is now a unique positive eigenvector (and thus a unique ranking).
answered Nov 27 '18 at 4:52
user1551user1551
72.4k566127
$endgroup$
$begingroup$
Thank you very much!
$endgroup$
– Jose
Nov 27 '18 at 4:58
$begingroup$
You could, however, apply the theorem to non-negative matrices that satisfy additional criteria. For instance, a unique eigenvector will exist if the matrix is irreducible and aperiodic (i.e. if the associated Markov chain is ergodic )
$endgroup$
– Omnomnomnom
Nov 27 '18 at 5:17
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3015342%2fperron-frobenius-theorem-modified%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The $5times5$ matrix is not positive. It has zero entries.
Remark. And that was probably the reason why Brin et al. introduced the so-called damping factor in their PageRank paper. Without the damping factor, their matrix is merely nonnegative and it might not possess a unique nonnegative eigenvector, i.e. the ranking is not unique. However, by introducing the damping factor (i.e. by considering a convex combination of their matrix with an all-one matrix), the matrix becomes positive and there is now a unique positive eigenvector (and thus a unique ranking).
answered Nov 27 '18 at 4:52
user1551user1551
72.4k566127
$endgroup$
$begingroup$
Thank you very much!
$endgroup$
– Jose
Nov 27 '18 at 4:58
$begingroup$
You could, however, apply the theorem to non-negative matrices that satisfy additional criteria. For instance, a unique eigenvector will exist if the matrix is irreducible and aperiodic (i.e. if the associated Markov chain is ergodic )
$endgroup$
– Omnomnomnom
Nov 27 '18 at 5:17
add a comment |
$begingroup$
The $5times5$ matrix is not positive. It has zero entries.
Remark. And that was probably the reason why Brin et al. introduced the so-called damping factor in their PageRank paper. Without the damping factor, their matrix is merely nonnegative and it might not possess a unique nonnegative eigenvector, i.e. the ranking is not unique. However, by introducing the damping factor (i.e. by considering a convex combination of their matrix with an all-one matrix), the matrix becomes positive and there is now a unique positive eigenvector (and thus a unique ranking).
answered Nov 27 '18 at 4:52
user1551user1551
72.4k566127
$endgroup$
$begingroup$
Thank you very much!
$endgroup$
– Jose
Nov 27 '18 at 4:58
$begingroup$
You could, however, apply the theorem to non-negative matrices that satisfy additional criteria. For instance, a unique eigenvector will exist if the matrix is irreducible and aperiodic (i.e. if the associated Markov chain is ergodic )
$endgroup$
– Omnomnomnom
Nov 27 '18 at 5:17
add a comment |
$begingroup$
The $5times5$ matrix is not positive. It has zero entries.
Remark. And that was probably the reason why Brin et al. introduced the so-called damping factor in their PageRank paper. Without the damping factor, their matrix is merely nonnegative and it might not possess a unique nonnegative eigenvector, i.e. the ranking is not unique. However, by introducing the damping factor (i.e. by considering a convex combination of their matrix with an all-one matrix), the matrix becomes positive and there is now a unique positive eigenvector (and thus a unique ranking).
answered Nov 27 '18 at 4:52
user1551user1551
72.4k566127
$endgroup$
The $5times5$ matrix is not positive. It has zero entries.
Remark. And that was probably the reason why Brin et al. introduced the so-called damping factor in their PageRank paper. Without the damping factor, their matrix is merely nonnegative and it might not possess a unique nonnegative eigenvector, i.e. the ranking is not unique. However, by introducing the damping factor (i.e. by considering a convex combination of their matrix with an all-one matrix), the matrix becomes positive and there is now a unique positive eigenvector (and thus a unique ranking).
answered Nov 27 '18 at 4:52
user1551user1551
72.4k566127
edited Nov 27 '18 at 5:31
answered Nov 27 '18 at 4:52
user1551user1551
72.4k566127
answered Nov 27 '18 at 4:52
user1551user1551
72.4k566127
answered Nov 27 '18 at 4:52
user1551user1551
72.4k566127
72.4k566127
$begingroup$
Thank you very much!
$endgroup$
– Jose
Nov 27 '18 at 4:58
$begingroup$
You could, however, apply the theorem to non-negative matrices that satisfy additional criteria. For instance, a unique eigenvector will exist if the matrix is irreducible and aperiodic (i.e. if the associated Markov chain is ergodic )
$endgroup$
– Omnomnomnom
Nov 27 '18 at 5:17
add a comment |
$begingroup$
Thank you very much!
$endgroup$
– Jose
Nov 27 '18 at 4:58
$begingroup$
You could, however, apply the theorem to non-negative matrices that satisfy additional criteria. For instance, a unique eigenvector will exist if the matrix is irreducible and aperiodic (i.e. if the associated Markov chain is ergodic )
$endgroup$
– Omnomnomnom
Nov 27 '18 at 5:17
$begingroup$
Thank you very much!
$endgroup$
– Jose
Nov 27 '18 at 4:58
$begingroup$
Thank you very much!
$endgroup$
– Jose
Nov 27 '18 at 4:58
$begingroup$
You could, however, apply the theorem to non-negative matrices that satisfy additional criteria. For instance, a unique eigenvector will exist if the matrix is irreducible and aperiodic (i.e. if the associated Markov chain is ergodic )
$endgroup$
– Omnomnomnom
Nov 27 '18 at 5:17
$begingroup$
You could, however, apply the theorem to non-negative matrices that satisfy additional criteria. For instance, a unique eigenvector will exist if the matrix is irreducible and aperiodic (i.e. if the associated Markov chain is ergodic )
$endgroup$
– Omnomnomnom
Nov 27 '18 at 5:17
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3015342%2fperron-frobenius-theorem-modified%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
