"페론-프로베니우스 정리 (Perron-Frobenius theorem)"의 두 판 사이의 차이

수학노트
둘러보기로 가기 검색하러 가기
 
(사용자 2명의 중간 판 30개는 보이지 않습니다)
1번째 줄: 1번째 줄:
<h5 style="margin: 0px; line-height: 3.428em; color: rgb(34, 61, 103); font-family: 'malgun gothic',dotum,gulim,sans-serif; font-size: 1.166em; background-position: 0px 100%;">이 항목의 수학노트 원문주소</h5>
+
==개요==
  
* [[페론-프로베니우스 정리 (Perron-Frobenius theorem)]]
+
* <em>A</em> = (<em>a</em><sub><em>ij</em></sub>) 가 <em>n</em> × <em>n</em> 양행렬, 즉  1 ≤ <em>i</em>, <em>j</em> ≤ <em>n </em> 에 대하여 <em>a</em><sub><em>ij</em></sub> > 0 가 성립한다고 가정하자
 +
*  다음이 성립한다
 +
**  A의 고유값 <math>r>0</math> 이 존재하여, 다른 고유값 λ에 대하여 부등식 |λ| < r가 성립한다.
 +
**  r 에 대응되는 고유벡터공간은 1차원이다
 +
**  r에 대응되는 모든 성분이 양수인 고유벡터 <em>v</em> = (<em>v</em><sub>1</sub>,…,<em>v</em><sub><em>n</em></sub>) 가 존재한다. 즉 <em>A v</em> = <em>r v</em>,  1 ≤ <em>i</em> ≤ <em>n</em> 에 대하여 <em>v</em><sub><em>i</em></sub> > 0 이 성립하도록 하는 v를 찾을수 있다
  
 
+
  
 
+
==예==
  
<h5>개요</h5>
+
카르탄 행렬 <math>\mathcal{C}(A_5)</math> 의 역행렬은
  
* <em>A</em> = (<em>a</em><sub><em>ij</em></sub>) 가 <em>n</em> × <em>n</em> 양행렬, 즉  1 ≤ <em>i</em>, <em>j</em> <em></em> 에 대하여 <em>a</em><sub><em>ij</em></sub> > 0 가 성립한다고 가정하자
+
<math>\left( \begin{array}{ccccc}  \frac{5}{6} & \frac{2}{3} & \frac{1}{2} & \frac{1}{3} & \frac{1}{6} \\  \frac{2}{3} & \frac{4}{3} & 1 & \frac{2}{3} & \frac{1}{3} \\  \frac{1}{2} & 1 & \frac{3}{2} & 1 & \frac{1}{2} \\  \frac{1}{3} & \frac{2}{3} & 1 & \frac{4}{3} & \frac{2}{3} \\  \frac{1}{6} & \frac{1}{3} & \frac{1}{2} & \frac{2}{3} & \frac{5}{6} \end{array} \right)</math>로 양행렬이다.
* 다음이 성립한다<br>
+
 
** A의 고유값 <math>r>0</math> 이 존재하여, 다른 고유값 λ에 대하여 부등식 |λ| < r가 성립한다.<br>
+
이 행렬의 고유값은 <math>2+\sqrt{3},1,\frac{1}{2},\frac{1}{3},2-\sqrt{3}</math>로 주어진다.
**  r 에 대응되는 고유벡터공간은 1차원이다<br>
+
 
**  r에 대응되는 모든 성분이 양수인 고유벡터 <em>v</em> = (<em>v</em><sub>1</sub>,…,<em>v</em><sub><em>n</em></sub>) 가 존재한다. 즉 <em>A v</em> = <em>r v</em>,  1 ≤ <em>i</em> ≤ <em>n</em> 에 대하여 <em>v</em><sub><em>i</em></sub> > 0 이 성립하도록 하는 v를 찾을수 있다<br>
+
벡터 <math>\left( \begin{array}{c}  1 \\  \sqrt{3} \\  2 \\  \sqrt{3} \\  1 \end{array} \right)</math> 는 고유값이 <math>2+\sqrt{3}</math>인 고유벡터이다.
 +
 
 +
 +
 
 +
   
 +
 
 +
   
 +
 
 +
==브라우어 부동점 정리의 응용==
 +
 
 +
<math>A\geq 0</math> : non-negative 행렬
 +
 
 +
<math>\sigma(A)</math> : A 의 스펙트럼, 즉 A의 고유값의 집합 <math>\sigma(A)=\{\lambda_1,\cdots, \lambda_{k}\}</math>
  
 
+
<math>\rho(A)</math> : A 의 spectral radius, <math>\{|\lambda_1|,\cdots, |\lambda_{k}|\}</math> 에서의 최대값
  
<h5></h5>
+
<math>\|\mathbf{x}\|_{1}</math> : L^1-norm of x, 즉 <math>\mathbf{x}=(x_1,\cdots, x_k)</math> 이면, <math>\|\mathbf{x}\|_{1}=|x_1|+\cdots+|x_k|</math>
  
카르탄 행렬 <math>\mathcal{C}(A_5)</math> 의 역행렬은
+
  
<math>\left( \begin{array}{ccccc}  \frac{5}{6} & \frac{2}{3} & \frac{1}{2} & \frac{1}{3} & \frac{1}{6} \\  \frac{2}{3} & \frac{4}{3} & 1 & \frac{2}{3} & \frac{1}{3} \\  \frac{1}{2} & 1 & \frac{3}{2} & 1 & \frac{1}{2} \\  \frac{1}{3} & \frac{2}{3} & 1 & \frac{4}{3} & \frac{2}{3} \\  \frac{1}{6} & \frac{1}{3} & \frac{1}{2} & \frac{2}{3} & \frac{5}{6} \end{array} \right)</math>로 양행렬이다.
+
(정리)
  
이 행렬의 고유값은 <math>2+\sqrt{3},1,\frac{1}{2},\frac{1}{3},2-\sqrt{3}</math>로 주어진다.
+
<math>\rho(A)</math> 는 A의 고유값이며, <math>\mathbf{x}\geq 0</math> 인 고유벡터가 존재한다.
  
벡터 <math>\left( \begin{array}{c} 1 \\  \sqrt{3} \\  2 \\  \sqrt{3} \\  1 \end{array} \right)</math> 는 고유값이 <math>2+\sqrt{3}</math>인 고유벡터이다.
+
   
  
 
+
(증명)
  
 
+
<math>K =\{\mathbf{x}\in\mathbb{R}^n|\mathbf{x}\geq 0,\|\mathbf{x}\|_{1}=1, A\mathbf{x}\geq \rho(A)\mathbf{x}\}</math> 라 두자.
  
 
+
<math>\lambda</math> 를 <math>|\lambda|=\rho(A)</math> 를 만족시키는 A의 고유값이라 하고, <math>\mathbf{v}</math> 를 대응되는 고유벡터라 두자. <math>\|\mathbf{v}\|_{1}=1</math> 로 둘 수 있다.
  
<h5>역사</h5>
+
<math>\rho(A)|\mathbf{v}|=|\lambda \mathbf{v}|=|A \mathbf{v}|\leq A|\mathbf{v}|</math> 이므로, <math>|\mathbf{v}|\in K</math> 이고, K는 공집합이 아니다.
  
 
+
따라서 K는 compact, convex, non-empty.
  
* http://www.google.com/search?hl=en&tbs=tl:1&q=
+
* [[수학사연표 (역사)|수학사연표]]
 
  
 
+
이제 두 가지 경우로 나눌 수 있다.
  
 
+
(1) <math>A\mathbf{x} = 0</math> 인 <math>\mathbf{x}\in K</math>가 존재하는 경우
  
<h5>메모</h5>
+
(2) 모든 <math>\mathbf{x}\in K</math> 에 대하여 <math>A\mathbf{x} \neq 0</math> 가 성립하는 경우
  
 
+
  
* Math Overflow http://mathoverflow.net/search?q=
+
(1) 의 경우는, <math>\rho(A)=0</math> 이 되어 증명이 끝난다.
  
 
+
(2) 의 경우를 생각하자.
  
 
+
<math>f : K\to \mathbb{R}^{n}</math> 을 <math>f(\mathbf{x})=\frac{A\mathbf{x}}{\|A\mathbf{x}\|_1}</math> 로 정의하자.
  
<h5>관련된 항목들</h5>
+
<math>f(\mathbf{x})\geq 0</math>, <math>\|f(\mathbf{x})\|_{1}=1</math> 임을 쉽게 알 수 있다. 또한,
  
* [[inverse positive matrix]]
+
<math>Af(\mathbf{x})=\frac{A (A\mathbf{x})}{\|A\mathbf{x}\|_1}\geq \frac{A (\rho(A)\mathbf{x})}{\|A\mathbf{x}\|_1}=\rho(A)f(\mathbf{x})</math> 이므로, <math>f(K)\subseteq K</math>.
  
 
+
  
 
+
따라서 [[브라우어 부동점 정리]] 에 의해, <math>f(\mathbf{y})=\mathbf{y}</math> 인 <math>\mathbf{y}\in K</math> 가 존재한다.
  
<h5 style="margin: 0px; line-height: 3.428em; color: rgb(34, 61, 103); font-family: 'malgun gothic',dotum,gulim,sans-serif; font-size: 1.166em; background-position: 0px 100%;">수학용어번역</h5>
+
<math>f(\mathbf{y})=\frac{A\mathbf{y}}{\|A\mathbf{y}\|_1}=\mathbf{y}</math> 이므로, <math>\|A\mathbf{y}\|_1=r</math> 로 두면, <math>A\mathbf{y}=r\mathbf{y}</math> 이다.
  
*  단어사전<br>
+
또한 <math>\mathbf{y}\in K</math> 이므로, <math>A\mathbf{y}=r\mathbf{y}\geq \rho(A)\mathbf{y}</math>.  
** http://translate.google.com/#en|ko|
 
** http://ko.wiktionary.org/wiki/
 
* 발음사전 http://www.forvo.com/search/
 
* [http://mathnet.kaist.ac.kr/mathnet/math_list.php?mode=list&ftype=&fstr= 대한수학회 수학 학술 용어집]<br>
 
** http://mathnet.kaist.ac.kr/mathnet/math_list.php?mode=list&ftype=eng_term&fstr=
 
* [http://www.kss.or.kr/pds/sec/dic.aspx 한국통계학회 통계학 용어 온라인 대조표]
 
* [http://www.nktech.net/science/term/term_l.jsp?l_mode=cate&s_code_cd=MA 남·북한수학용어비교]
 
* [http://kms.or.kr/home/kor/board/bulletin_list_subject.asp?bulletinid=%7BD6048897-56F9-43D7-8BB6-50B362D1243A%7D&boardname=%BC%F6%C7%D0%BF%EB%BE%EE%C5%E4%B7%D0%B9%E6&globalmenu=7&localmenu=4 대한수학회 수학용어한글화 게시판]
 
  
 
+
따라서 <math>r=\rho(A)</math>은 A의 고유값이며, <math>\mathbf{y}\geq 0</math> 는 대응되는 고유벡터이다. ■
  
 
+
  
<h5>매스매티카 파일 및 계산 리소스</h5>
+
  
* https://docs.google.com/file/d/0B8XXo8Tve1cxTGpWWGN0dGhudUU/edit?pli=1
+
==메모==
* http://www.wolframalpha.com/input/?i=
 
* http://functions.wolfram.com/
 
* [http://dlmf.nist.gov/ NIST Digital Library of Mathematical Functions]
 
* [http://people.math.sfu.ca/%7Ecbm/aands/toc.htm Abramowitz and Stegun Handbook of mathematical functions]
 
* [http://www.research.att.com/%7Enjas/sequences/index.html The On-Line Encyclopedia of Integer Sequences]
 
* [http://numbers.computation.free.fr/Constants/constants.html Numbers, constants and computation]
 
* [https://docs.google.com/open?id=0B8XXo8Tve1cxMWI0NzNjYWUtNmIwZi00YzhkLTkzNzQtMDMwYmVmYmIxNmIw 매스매티카 파일 목록]
 
  
 
+
* [http://people.ciram.unibo.it/%7Esgallari/Meetings/Matrix_day/benzi.ps http://people.ciram.unibo.it/~sgallari/Meetings/Matrix_day/benzi.ps]
  
 
+
  
<h5>사전 형태의 자료</h5>
+
==관련된 항목들==
  
* http://ko.wikipedia.org/wiki/
+
* [[inverse positive matrix]]
* [http://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem http://en.wikipedia.org/wiki/Perron–Frobenius_theorem]
+
* [[브라우어 부동점 정리]]
* http://en.wikipedia.org/wiki/Nonnegative_matrix
 
* [http://eom.springer.de/default.htm The Online Encyclopaedia of Mathematics]
 
* [http://dlmf.nist.gov NIST Digital Library of Mathematical Functions]
 
* [http://eqworld.ipmnet.ru/ The World of Mathematical Equations]
 
  
 
 
  
 
+
  
<h5>리뷰논문, 에세이, 강의노트</h5>
+
==매스매티카 파일 및 계산 리소스==
 +
* https://docs.google.com/file/d/0B8XXo8Tve1cxTGpWWGN0dGhudUU/edit?pli=1
  
* [http://www.imsc.res.in/%7Esunder/pf.pdf ][http://www.imsc.res.in/%7Esunder/pf.pdf http://www.imsc.res.in/~sunder/pf.pdf]<br>
+
** 페론-프로베니우스 in graph theory, fusion algebra
+
  
 
+
==사전 형태의 자료==
 +
* http://en.wikipedia.org/wiki/Perron–Frobenius_theorem
 +
* http://en.wikipedia.org/wiki/Nonnegative_matrix
  
 
+
  
 
+
==리뷰, 에세이, 강의노트==
 +
* Hawkins, Thomas. 2008. “Continued Fractions and the Origins of the Perron–Frobenius Theorem.” Archive for History of Exact Sciences 62 (6) (November 1): 655–717. doi:10.1007/s00407-008-0026-x.
 +
* [http://www.imsc.res.in/%7Esunder/pf.pdf http://www.imsc.res.in/~sunder/pf.pdf]
 +
** 페론-프로베니우스 in graph theory, fusion algebra, ...
  
<h5>관련논문</h5>
 
  
* http://www.jstor.org/action/doBasicSearch?Query=
+
* http://www.ams.org/mathscinet
+
==관련논문==
* http://dx.doi.org/
+
* Martin Lustig, Caglar Uyanik, Perron-Frobenius theory and frequency convergence for reducible substitutions, arXiv:1605.02242 [math.DS], May 07 2016, http://arxiv.org/abs/1605.02242
 +
* Robert Costa, Patrick Dynes, Clayton Petsche, A p-adic Perron-Frobenius Theorem, arXiv:1509.01702[math.NT], September 05 2015, http://arxiv.org/abs/1509.01702v2
 +
* Meyer, Carl D. “Continuity of the Perron Root.” Linear and Multilinear Algebra, July 3, 2014, 1–5. doi:10.1080/03081087.2014.934233.
  
 
 
  
 
+
  
<h5>관련도서</h5>
+
==관련도서==
  
 
* Henryk Minc, Nonnegative matrices, John Wiley&Sons, New York, 1988, ISBN 0-471-83966-3
 
* Henryk Minc, Nonnegative matrices, John Wiley&Sons, New York, 1988, ISBN 0-471-83966-3
도서내검색<br>
+
 
** http://books.google.com/books?q=
+
[[분류:선형대수학]]
** http://book.daum.net/search/contentSearch.do?query=
+
 
 +
==메타데이터==
 +
===위키데이터===
 +
* ID : [https://www.wikidata.org/wiki/Q1564541 Q1564541]
 +
===Spacy 패턴 목록===
 +
* [{'LOWER': 'perron'}, {'OP': '*'}, {'LOWER': 'frobenius'}, {'LEMMA': 'theorem'}]

2021년 2월 17일 (수) 05:05 기준 최신판

개요

  • A = (aij) 가 n × n 양행렬, 즉 1 ≤ i, jn 에 대하여 aij > 0 가 성립한다고 가정하자
  • 다음이 성립한다
    • A의 고유값 \(r>0\) 이 존재하여, 다른 고유값 λ에 대하여 부등식 |λ| < r가 성립한다.
    • r 에 대응되는 고유벡터공간은 1차원이다
    • r에 대응되는 모든 성분이 양수인 고유벡터 v = (v1,…,vn) 가 존재한다. 즉 A v = r v, 1 ≤ in 에 대하여 vi > 0 이 성립하도록 하는 v를 찾을수 있다


카르탄 행렬 \(\mathcal{C}(A_5)\) 의 역행렬은

\(\left( \begin{array}{ccccc} \frac{5}{6} & \frac{2}{3} & \frac{1}{2} & \frac{1}{3} & \frac{1}{6} \\ \frac{2}{3} & \frac{4}{3} & 1 & \frac{2}{3} & \frac{1}{3} \\ \frac{1}{2} & 1 & \frac{3}{2} & 1 & \frac{1}{2} \\ \frac{1}{3} & \frac{2}{3} & 1 & \frac{4}{3} & \frac{2}{3} \\ \frac{1}{6} & \frac{1}{3} & \frac{1}{2} & \frac{2}{3} & \frac{5}{6} \end{array} \right)\)로 양행렬이다.

이 행렬의 고유값은 \(2+\sqrt{3},1,\frac{1}{2},\frac{1}{3},2-\sqrt{3}\)로 주어진다.

벡터 \(\left( \begin{array}{c} 1 \\ \sqrt{3} \\ 2 \\ \sqrt{3} \\ 1 \end{array} \right)\) 는 고유값이 \(2+\sqrt{3}\)인 고유벡터이다.




브라우어 부동점 정리의 응용

\(A\geq 0\) : non-negative 행렬

\(\sigma(A)\) : A 의 스펙트럼, 즉 A의 고유값의 집합 \(\sigma(A)=\{\lambda_1,\cdots, \lambda_{k}\}\)

\(\rho(A)\) : A 의 spectral radius, \(\{|\lambda_1|,\cdots, |\lambda_{k}|\}\) 에서의 최대값

\(\|\mathbf{x}\|_{1}\) : L^1-norm of x, 즉 \(\mathbf{x}=(x_1,\cdots, x_k)\) 이면, \(\|\mathbf{x}\|_{1}=|x_1|+\cdots+|x_k|\)


(정리)

\(\rho(A)\) 는 A의 고유값이며, \(\mathbf{x}\geq 0\) 인 고유벡터가 존재한다.


(증명)

\(K =\{\mathbf{x}\in\mathbb{R}^n|\mathbf{x}\geq 0,\|\mathbf{x}\|_{1}=1, A\mathbf{x}\geq \rho(A)\mathbf{x}\}\) 라 두자.

\(\lambda\) 를 \(|\lambda|=\rho(A)\) 를 만족시키는 A의 고유값이라 하고, \(\mathbf{v}\) 를 대응되는 고유벡터라 두자. \(\|\mathbf{v}\|_{1}=1\) 로 둘 수 있다.

\(\rho(A)|\mathbf{v}|=|\lambda \mathbf{v}|=|A \mathbf{v}|\leq A|\mathbf{v}|\) 이므로, \(|\mathbf{v}|\in K\) 이고, K는 공집합이 아니다.

따라서 K는 compact, convex, non-empty.


이제 두 가지 경우로 나눌 수 있다.

(1) \(A\mathbf{x} = 0\) 인 \(\mathbf{x}\in K\)가 존재하는 경우

(2) 모든 \(\mathbf{x}\in K\) 에 대하여 \(A\mathbf{x} \neq 0\) 가 성립하는 경우


(1) 의 경우는, \(\rho(A)=0\) 이 되어 증명이 끝난다.

(2) 의 경우를 생각하자.

\(f : K\to \mathbb{R}^{n}\) 을 \(f(\mathbf{x})=\frac{A\mathbf{x}}{\|A\mathbf{x}\|_1}\) 로 정의하자.

\(f(\mathbf{x})\geq 0\), \(\|f(\mathbf{x})\|_{1}=1\) 임을 쉽게 알 수 있다. 또한,

\(Af(\mathbf{x})=\frac{A (A\mathbf{x})}{\|A\mathbf{x}\|_1}\geq \frac{A (\rho(A)\mathbf{x})}{\|A\mathbf{x}\|_1}=\rho(A)f(\mathbf{x})\) 이므로, \(f(K)\subseteq K\).


따라서 브라우어 부동점 정리 에 의해, \(f(\mathbf{y})=\mathbf{y}\) 인 \(\mathbf{y}\in K\) 가 존재한다.

\(f(\mathbf{y})=\frac{A\mathbf{y}}{\|A\mathbf{y}\|_1}=\mathbf{y}\) 이므로, \(\|A\mathbf{y}\|_1=r\) 로 두면, \(A\mathbf{y}=r\mathbf{y}\) 이다.

또한 \(\mathbf{y}\in K\) 이므로, \(A\mathbf{y}=r\mathbf{y}\geq \rho(A)\mathbf{y}\).

따라서 \(r=\rho(A)\)은 A의 고유값이며, \(\mathbf{y}\geq 0\) 는 대응되는 고유벡터이다. ■



메모


관련된 항목들



매스매티카 파일 및 계산 리소스



사전 형태의 자료


리뷰, 에세이, 강의노트

  • Hawkins, Thomas. 2008. “Continued Fractions and the Origins of the Perron–Frobenius Theorem.” Archive for History of Exact Sciences 62 (6) (November 1): 655–717. doi:10.1007/s00407-008-0026-x.
  • http://www.imsc.res.in/~sunder/pf.pdf
    • 페론-프로베니우스 in graph theory, fusion algebra, ...


관련논문

  • Martin Lustig, Caglar Uyanik, Perron-Frobenius theory and frequency convergence for reducible substitutions, arXiv:1605.02242 [math.DS], May 07 2016, http://arxiv.org/abs/1605.02242
  • Robert Costa, Patrick Dynes, Clayton Petsche, A p-adic Perron-Frobenius Theorem, arXiv:1509.01702[math.NT], September 05 2015, http://arxiv.org/abs/1509.01702v2
  • Meyer, Carl D. “Continuity of the Perron Root.” Linear and Multilinear Algebra, July 3, 2014, 1–5. doi:10.1080/03081087.2014.934233.



관련도서

  • Henryk Minc, Nonnegative matrices, John Wiley&Sons, New York, 1988, ISBN 0-471-83966-3

메타데이터

위키데이터

Spacy 패턴 목록

  • [{'LOWER': 'perron'}, {'OP': '*'}, {'LOWER': 'frobenius'}, {'LEMMA': 'theorem'}]