Perron Frobenius Theorem modified
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 at 4:49
Jose
31
add a comment |
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 at 4:49
Jose
31
add a comment |
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 at 4:49
Jose
31
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 at 4:49
Jose
31
asked Nov 27 at 4:49
Jose
31
asked Nov 27 at 4:49
Jose
31
asked Nov 27 at 4:49
Jose
31
asked Nov 27 at 4:49
Jose
31
31
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
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 at 4:52
user1551
71.3k566125
Thank you very much!
– Jose
Nov 27 at 4:58
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 )
– Omnomnomnom
Nov 27 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
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 at 4:52
user1551
71.3k566125
Thank you very much!
– Jose
Nov 27 at 4:58
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 )
– Omnomnomnom
Nov 27 at 5:17
add a comment |
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 at 4:52
user1551
71.3k566125
Thank you very much!
– Jose
Nov 27 at 4:58
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 )
– Omnomnomnom
Nov 27 at 5:17
add a comment |
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 at 4:52
user1551
71.3k566125
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 at 4:52
user1551
71.3k566125
edited Nov 27 at 5:31
answered Nov 27 at 4:52
user1551
71.3k566125
answered Nov 27 at 4:52
user1551
71.3k566125
answered Nov 27 at 4:52
user1551
71.3k566125
71.3k566125
Thank you very much!
– Jose
Nov 27 at 4:58
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 )
– Omnomnomnom
Nov 27 at 5:17
add a comment |
Thank you very much!
– Jose
Nov 27 at 4:58
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 )
– Omnomnomnom
Nov 27 at 5:17
Thank you very much!
– Jose
Nov 27 at 4:58
Thank you very much!
– Jose
Nov 27 at 4:58
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 )
– Omnomnomnom
Nov 27 at 5:17
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 )
– Omnomnomnom
Nov 27 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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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
