הבדלים בין גרסאות בדף "קוד:פולינום אופייני ומינימלי של מטריצה אלכסונית בלוקים"
מ (7 גרסאות יובאו) |
|||
| (3 גרסאות ביניים של משתמש אחר אחד אינן מוצגות) | |||
| שורה 1: | שורה 1: | ||
הגדרנו מטריצות אלכסוניות בלוקים, וכעת ננסה לראות האם נוכל למצוא לה פולינום אופייני ומינימלי מבלי להתחיל לחשב אותם בכל פעם מחדש. | הגדרנו מטריצות אלכסוניות בלוקים, וכעת ננסה לראות האם נוכל למצוא לה פולינום אופייני ומינימלי מבלי להתחיל לחשב אותם בכל פעם מחדש. | ||
| − | \ | + | \begin{prop} |
תהי $A$ מטריצה אלכסונית בלוקים. אזי: | תהי $A$ מטריצה אלכסונית בלוקים. אזי: | ||
| שורה 7: | שורה 7: | ||
\begin{enumerate} | \begin{enumerate} | ||
| − | \item $p_A\left(x \right )=p_{A_1}\left(x \right )\dots p_{A_k}\left(x \right )$ | + | \item $$p_A\left(x \right )=p_{A_1}\left(x \right )\dots p_{A_k}\left(x \right )$$ |
| − | \item $m_A\left(x \right )=lcm \left \{m_{A_1}\left(x \right ),\dots, m_{A_k}\left(x \right ) \right \}$ | + | \item $$m_A\left(x \right )=\operatorname{lcm}\left \{m_{A_1}\left(x \right ),\dots, m_{A_k}\left(x \right ) \right \}$$ |
\end{enumerate} | \end{enumerate} | ||
| + | |||
| + | \end{prop} | ||
\underline{תזכורת:} | \underline{תזכורת:} | ||
למספרים טבעיים, | למספרים טבעיים, | ||
| − | $lcm \left \{a_1,\dots,a_k \right \}=\min\left\{M\mid a_1|M,\dots,a_k|M\right\}$. | + | $\operatorname{lcm} \left \{a_1,\dots,a_k \right \}=\min\left\{M\mid a_1|M,\dots,a_k|M\right\}$. |
לפולינומים, זהו הפולינום המתוקן מהמעלה הקטנה ביותר מהקבוצה | לפולינומים, זהו הפולינום המתוקן מהמעלה הקטנה ביותר מהקבוצה | ||
$\left \{ g\in\mathbb{F}\left[x \right ]\mid f_1|g,\dots,f_k|g \right \}$. | $\left \{ g\in\mathbb{F}\left[x \right ]\mid f_1|g,\dots,f_k|g \right \}$. | ||
| − | \ | + | \begin{proof} |
נסמן $p_{A_i}\left(x \right )=p_i\left(x \right )$, | נסמן $p_{A_i}\left(x \right )=p_i\left(x \right )$, | ||
| שורה 29: | שורה 31: | ||
לפי משפט קודם, | לפי משפט קודם, | ||
| − | + | $$m_1\left(x \right )|p_1\left(x \right )|\left[m_1\left(x \right ) \right ]^n,\cdots,m_k\left(x \right )|p_k\left(x \right )|\left[m_k\left(x \right ) \right ]^n$$ | |
| − | $ | + | נסמן $g\left(x \right )=\operatorname{lcm} \left \{m_{A_1}\left(x \right ),\dots, m_{A_k}\left(x \right ) \right \}$. נוכיח $m_A=g$ לפי השלבים הבאים: |
| − | \ | + | |
| − | + | ||
| − | + | ||
| − | m_k\left(x \right )|p_k\left(x \right )|\left[m_k\left(x \right ) \right ]^n$ | + | |
| − | + | ||
| − | נסמן $g\left(x \right )=lcm \left \{m_{A_1}\left(x \right ),\dots, m_{A_k}\left(x \right ) \right \}$. נוכיח $m_A=g$ לפי השלבים הבאים: | + | |
\begin{enumerate} | \begin{enumerate} | ||
\item אם $f\in\mathbb{F}\left[x\right]$ פולינום כלשהו, אזי | \item אם $f\in\mathbb{F}\left[x\right]$ פולינום כלשהו, אזי | ||
| − | $f\left(A \right )=\left(\begin{matrix} | + | $$f\left(A \right )=\left(\begin{matrix} |
| − | f\left(A_1 \right ) & &0 \\ | + | \begin{array}{c|}f\left (A_1 \right )\\\hline \end{array} & & 0\\ |
| − | &\ddots | + | & \ddots & \\ |
| − | 0 & & f\left(A_k \right ) | + | 0 & & \begin{array}{|c}\hline f\left(A_k \right ) \end{array} |
| − | \end{matrix} \right )$ | + | \end{matrix} \right )$$ |
זה נכון מפני שמתקיים: | זה נכון מפני שמתקיים: | ||
| שורה 51: | שורה 47: | ||
\begin{enumerate} | \begin{enumerate} | ||
| − | \item $A^\ell=\left(\begin{matrix} | + | \item $$A^\ell=\left(\begin{matrix} |
| − | A_1^\ell & &0 \\ | + | \begin{array}{c|}A_1^\ell \\\hline \end{array} & & 0\\ |
| − | &\ddots | + | & \ddots & \\ |
| − | 0 & & A_k^\ell | + | 0 & & \begin{array}{|c}\hline A_k^\ell \end{array} |
| − | \end{matrix} \right )$ | + | \end{matrix} \right )$$ |
| − | \item $\alpha A=\left(\begin{matrix} | + | \item $$\alpha A=\left(\begin{matrix} |
| − | \alpha A_1 & &0 \\ | + | \begin{array}{c|}\alpha A_1 \\\hline \end{array} & & 0\\ |
| − | &\ddots | + | & \ddots & \\ |
| − | 0 & & \alpha A_k | + | 0 & & \begin{array}{|c}\hline \alpha A_k \end{array} |
| − | \end{matrix} \right )$ | + | \end{matrix} \right )$$ |
| − | \item אם $A,\tilde{A}$ שתי מטריצות אלכסוניות בלוקים כשהבלוקים מאותו גודל | + | \item אם $A,\tilde{A}$ שתי מטריצות אלכסוניות בלוקים כשהבלוקים מאותו גודל (מטריצות מאותו מבנה), אזי |
| − | + | $$A+\tilde{A}=\left(\begin{matrix} | |
| − | $A+\tilde{A}=\left(\begin{matrix} | + | \begin{array}{c|}A_1+\tilde{A}_1 \\\hline \end{array} & & 0\\ |
| − | A_1+\tilde{A}_1 & &0 \\ | + | & \ddots & \\ |
| − | &\ddots | + | 0 & & \begin{array}{|c}\hline A_k+\tilde{A}_k \end{array} |
| − | 0 & & A_k+\tilde{A}_k | + | \end{matrix} \right )$$ |
| − | \end{matrix} \right )$ | + | |
\end{enumerate} | \end{enumerate} | ||
| שורה 75: | שורה 70: | ||
\item אם $f\left(A\right)=0$, אזי $f\left(A_i\right)=0$ לכל $i=1,\dots,k$. | \item אם $f\left(A\right)=0$, אזי $f\left(A_i\right)=0$ לכל $i=1,\dots,k$. | ||
| − | \item $m_A\left(A_i \right )=0$ לכל $i=1,\dots,k$ | + | \item $m_A\left(A_i \right )=0$ לכל $i=1,\dots,k$ (לפי השלב הקודם). |
\item לכל $i=1,\dots,k$, מתקיים $m_i|m_A$. נימוק: נשתמש בחילוק עם שארית. | \item לכל $i=1,\dots,k$, מתקיים $m_i|m_A$. נימוק: נשתמש בחילוק עם שארית. | ||
| שורה 81: | שורה 76: | ||
$m_A=q\cdot m_i+r$, כאשר $\deg\left(r\right)<\deg\left(m_i\right)$ או $r=0$. נציב $A_i$, ונקבל $m_A\left ( A_i \right )=q\left ( A_i \right )\cdot m_i\left ( A_i \right )+r\left ( A_i \right )$, כלומר $0=q\left ( A_i \right )\cdot 0+r\left ( A_i \right )$, ומכאן $r\left ( A_i \right )=0$. לכן, אם $\deg\left(r\right)<\deg\left(m_i\right)$, נקבל סתירה למינימליות של $m_i$, כלומר $r=0$. | $m_A=q\cdot m_i+r$, כאשר $\deg\left(r\right)<\deg\left(m_i\right)$ או $r=0$. נציב $A_i$, ונקבל $m_A\left ( A_i \right )=q\left ( A_i \right )\cdot m_i\left ( A_i \right )+r\left ( A_i \right )$, כלומר $0=q\left ( A_i \right )\cdot 0+r\left ( A_i \right )$, ומכאן $r\left ( A_i \right )=0$. לכן, אם $\deg\left(r\right)<\deg\left(m_i\right)$, נקבל סתירה למינימליות של $m_i$, כלומר $r=0$. | ||
| − | \item אם כן, $g|m_A$, כי $g$ הוא $\lcm$. | + | \item אם כן, $g|m_A$, כי $g$ הוא $\operatorname{lcm}$. |
\item עם זאת, $g\left ( A_i \right )=0$ לכל $i=1,\dots,k$, כי לכל $i$, מתקיים $m_i\left(A_i\right)=0$, וכן ידוע $m_i|g$. | \item עם זאת, $g\left ( A_i \right )=0$ לכל $i=1,\dots,k$, כי לכל $i$, מתקיים $m_i\left(A_i\right)=0$, וכן ידוע $m_i|g$. | ||
| שורה 92: | שורה 87: | ||
\end{enumerate} | \end{enumerate} | ||
| + | |||
| + | \end{proof} | ||
גרסה אחרונה מ־20:16, 4 באוקטובר 2014
הגדרנו מטריצות אלכסוניות בלוקים, וכעת ננסה לראות האם נוכל למצוא לה פולינום אופייני ומינימלי מבלי להתחיל לחשב אותם בכל פעם מחדש.
\begin{prop}
תהי $A$ מטריצה אלכסונית בלוקים. אזי:
\begin{enumerate}
\item $$p_A\left(x \right )=p_{A_1}\left(x \right )\dots p_{A_k}\left(x \right )$$
\item $$m_A\left(x \right )=\operatorname{lcm}\left \{m_{A_1}\left(x \right ),\dots, m_{A_k}\left(x \right ) \right \}$$
\end{enumerate}
\end{prop}
\underline{תזכורת:}
למספרים טבעיים, $\operatorname{lcm} \left \{a_1,\dots,a_k \right \}=\min\left\{M\mid a_1|M,\dots,a_k|M\right\}$.
לפולינומים, זהו הפולינום המתוקן מהמעלה הקטנה ביותר מהקבוצה $\left \{ g\in\mathbb{F}\left[x \right ]\mid f_1|g,\dots,f_k|g \right \}$.
\begin{proof}
נסמן $p_{A_i}\left(x \right )=p_i\left(x \right )$, $m_{A_i}\left(x \right )=m_i\left(x \right )$.
החלק הראשון על הפולינום האופייני קל לחישוב ישירות, על ידי דטרמיננטה של מטריצת בלוקים. אם כן, נוכיח רק את החלק השני.
לפי משפט קודם, $$m_1\left(x \right )|p_1\left(x \right )|\left[m_1\left(x \right ) \right ]^n,\cdots,m_k\left(x \right )|p_k\left(x \right )|\left[m_k\left(x \right ) \right ]^n$$ נסמן $g\left(x \right )=\operatorname{lcm} \left \{m_{A_1}\left(x \right ),\dots, m_{A_k}\left(x \right ) \right \}$. נוכיח $m_A=g$ לפי השלבים הבאים:
\begin{enumerate}
\item אם $f\in\mathbb{F}\left[x\right]$ פולינום כלשהו, אזי $$f\left(A \right )=\left(\begin{matrix} \begin{array}{c|}f\left (A_1 \right )\\\hline \end{array} & & 0\\
& \ddots & \\
0 & & \begin{array}{|c}\hline f\left(A_k \right ) \end{array} \end{matrix} \right )$$
זה נכון מפני שמתקיים:
\begin{enumerate}
\item $$A^\ell=\left(\begin{matrix} \begin{array}{c|}A_1^\ell \\\hline \end{array} & & 0\\
& \ddots & \\
0 & & \begin{array}{|c}\hline A_k^\ell \end{array} \end{matrix} \right )$$
\item $$\alpha A=\left(\begin{matrix} \begin{array}{c|}\alpha A_1 \\\hline \end{array} & & 0\\
& \ddots & \\
0 & & \begin{array}{|c}\hline \alpha A_k \end{array} \end{matrix} \right )$$
\item אם $A,\tilde{A}$ שתי מטריצות אלכסוניות בלוקים כשהבלוקים מאותו גודל (מטריצות מאותו מבנה), אזי $$A+\tilde{A}=\left(\begin{matrix} \begin{array}{c|}A_1+\tilde{A}_1 \\\hline \end{array} & & 0\\
& \ddots & \\
0 & & \begin{array}{|c}\hline A_k+\tilde{A}_k \end{array} \end{matrix} \right )$$
\end{enumerate}
\item אם $f\left(A\right)=0$, אזי $f\left(A_i\right)=0$ לכל $i=1,\dots,k$.
\item $m_A\left(A_i \right )=0$ לכל $i=1,\dots,k$ (לפי השלב הקודם).
\item לכל $i=1,\dots,k$, מתקיים $m_i|m_A$. נימוק: נשתמש בחילוק עם שארית.
$m_A=q\cdot m_i+r$, כאשר $\deg\left(r\right)<\deg\left(m_i\right)$ או $r=0$. נציב $A_i$, ונקבל $m_A\left ( A_i \right )=q\left ( A_i \right )\cdot m_i\left ( A_i \right )+r\left ( A_i \right )$, כלומר $0=q\left ( A_i \right )\cdot 0+r\left ( A_i \right )$, ומכאן $r\left ( A_i \right )=0$. לכן, אם $\deg\left(r\right)<\deg\left(m_i\right)$, נקבל סתירה למינימליות של $m_i$, כלומר $r=0$.
\item אם כן, $g|m_A$, כי $g$ הוא $\operatorname{lcm}$.
\item עם זאת, $g\left ( A_i \right )=0$ לכל $i=1,\dots,k$, כי לכל $i$, מתקיים $m_i\left(A_i\right)=0$, וכן ידוע $m_i|g$.
\item לכן, $g\left ( A \right )=0$.
\item אם כן, $g|m_A$.
\item מ-5, מ-8 ומהעובדה ששני הפולינומים מתוקנים, נקבל $g=m_A$, כדרוש.
\end{enumerate}
\end{proof}
