उच्च माध्यमिक गणित · Bovenbouw

30आव्यूह और ग्राफ़

आव्यूह संख्याओं की आयताकार सारणी है, जिसे जोड़ने और गुणा करने के नियम इस तरह गढ़े गए हैं कि आव्यूह-बीजगणित रैखिक रूपांतरणों के संयोजन को दर्शा सके। आव्यूह रैखिक निकाय हल करते हैं, युग्मित पुनरावर्ती अनुक्रम चलाते हैं, और जालों में चालें गिनते हैं — यही गणित खोज-इंजनों और सबसे छोटे रास्ते की कलनविधियों के पीछे है।

30.1 आव्यूह-बीजगणित

परिभाषा 30.1 (आव्यूह)

$m \times n$ आव्यूह वास्तविक संख्याओं की ऐसी सारणी है जिसमें $m$ पंक्तियाँ और $n$ स्तंभ हों: $A = (a_{ij})$ , जहाँ $a_{ij}$ पंक्ति $i$ , स्तंभ $j$ की प्रविष्टि है। एक ही आकार के दो आव्यूह प्रविष्टि-दर-प्रविष्टि जोड़े जाते हैं, और $\lambda A = (\lambda a_{ij})$ ।

परिभाषा 30.2 (आव्यूह गुणनफल)

मान लीजिए $A$ $m \times n$ का है और $B$ $n \times p$ का। गुणनफल $AB$ वह $m \times p$ आव्यूह है जिसकी $(i,j)$ प्रविष्टि

(AB)_{ij} = \sum_{k=1}^{n} a_{ik} b_{kj}

है (“ $A$ की पंक्ति $i$ गुणा $B$ का स्तंभ $j$ ” वाला नियम)।

उदाहरण 30.3

$\begin{pmatrix} 1 & 2\\ 3 & 4\end{pmatrix} \begin{pmatrix} 0 & 1\\ 1 & 1\end{pmatrix} = \begin{pmatrix} 2 & 3\\ 4 & 7\end{pmatrix}$ , जबकि $\begin{pmatrix} 0 & 1\\ 1 & 1\end{pmatrix} \begin{pmatrix} 1 & 2\\ 3 & 4\end{pmatrix} = \begin{pmatrix} 3 & 4\\ 4 & 6\end{pmatrix}$ : आव्यूहों का गुणन क्रमविनिमेय नहीं है।

प्रतिज्ञप्ति 30.4 (आव्यूह-बीजगणित के नियम)

जब भी आकार गुणनफलों को अर्थपूर्ण बनाते हों:

(AB)C = A(BC), \qquad A(B + C) = AB + AC, \qquad (A+B)C = AC + BC,

और तत्समक आव्यूह $I_n$ (विकर्ण पर एक, अन्यत्र शून्य) $m \times n$ आकार वाले $A$ के लिए $I_m A = A I_n = A$ संतुष्ट करता है।

उपपत्ति. सभी परिभाषा 30.2 से प्रविष्टि-दर-प्रविष्टि सत्यापन हैं; साहचर्य, जो अकेला अ-तुच्छ है, वस्तुतः दो परिमित योगों की अदला-बदली ही है: $\bigl((AB)C\bigr)_{ij} = \sum_l \left(\sum_k a_{ik}b_{kl}\right) c_{lj} = \sum_k a_{ik} \left(\sum_l b_{kl} c_{lj}\right) = \bigl(A(BC)\bigr)_{ij}$ । ∎

परिभाषा 30.5 (प्रतिलोम)

$n$ आकार का कोई वर्ग आव्यूह $A$ प्रतिलोमनीय है यदि ऐसा आव्यूह $B$ हो कि $AB = BA = I_n$ हो; तब $B$ अद्वितीय होता है और उसे $A^{-1}$ लिखते हैं।

प्रतिज्ञप्ति 30.6 ( $2\times2$ आव्यूह का प्रतिलोम)

मान लीजिए $A = \begin{pmatrix} a & b\\ c & d\end{pmatrix}$ और $\det A = ad - bc$ (सारणिक) हैं। तब $A$ प्रतिलोमनीय है यदि और केवल यदि $\det A \neq 0$ हो, और उस स्थिति में

A^{-1} = \frac{1}{ad - bc}\begin{pmatrix} d & -b\\ -c & a\end{pmatrix}.

उपपत्ति. एक गणना $A \begin{pmatrix} d & -b\\ -c & a\end{pmatrix} = \begin{pmatrix} d & -b\\ -c & a\end{pmatrix} A = (ad - bc) I_2$ देती है; यदि $ad - bc \neq 0$ हो तो भाग दे दीजिए। इसके उलट, यदि $ad - bc = 0$ हो तो $A$ के स्तंभ समानुपाती होते हैं, और किसी भी $B$ के लिए $AB$ के स्तंभ भी; पर $I_2$ के स्तंभ समानुपाती नहीं हैं, इसलिए कोई $B$ $AB = I_2$ को संतुष्ट नहीं कर सकता। ∎

विधि 30.7 (रैखिक निकाय)

निकाय $\begin{cases} ax + by = e\\ cx + dy = f \end{cases}$ $X = \begin{pmatrix} x \\ y\end{pmatrix}$ , $Y = \begin{pmatrix} e \\ f\end{pmatrix}$ के साथ आव्यूह समीकरण $AX = Y$ है। यदि $\det A \neq 0$ हो, तो उसका अद्वितीय हल $X = A^{-1}Y$ है। यही औपचारिकता $n$ अज्ञातों में $n$ समीकरण भी सँभाल लेती है।

30.2 आव्यूह की घातें और पुनरावर्ती अनुक्रम

परिभाषा 30.8

किसी वर्ग आव्यूह $A$ और $k \in \N$ के लिए $A^k = A \times \dots \times A$ ( $k$ गुणनखंड), और $A^0 = I$ ।

विधि 30.9 (विकर्ण-जमा-शून्यघाती और विकर्णीयकरणीय स्थितियाँ)

$A^k$ निकालने के दो मानक तरीक़े:

यदि $A = \lambda I + N$ हो, जहाँ $N^2 = 0$ , तो द्विपद प्रमेय (यहाँ वैध, क्योंकि $I$ और $N$ क्रमविनिमेय हैं) सिमटकर दो पदों में आ जाती है: $A^k = \lambda^k I + k \lambda^{k-1} N$ ।
यदि ऐसा प्रतिलोमनीय $P$ मिल जाए कि $A = PDP^{-1}$ हो और $D$ विकर्ण हो, तो $A^k = P D^k P^{-1}$ , और $D^k$ प्रविष्टि-दर-प्रविष्टि निकल आता है। (ऐसा $P$ व्यवस्थित ढंग से ढूँढ़ना विकर्णीकरण का सिद्धांत है, जो स्नातक स्तर पर विकसित होता है; इस स्तर पर $P$ दे दिया जाता है।)

उदाहरण 30.10 (युग्मित अनुक्रम)

मान लीजिए $u_{n+1} = 3u_n + v_n$ और $v_{n+1} = u_n + 3v_n$ हैं। $X_n = \begin{pmatrix} u_n\\ v_n \end{pmatrix}$ और $A = \begin{pmatrix} 3 & 1\\ 1 & 3\end{pmatrix}$ रखने पर $X_{n+1} = AX_n$ मिलता है, इसलिए $X_n = A^n X_0$ । सहायक अनुक्रम $s_n = u_n + v_n$ और $d_n = u_n - v_n$ $s_{n+1} = 4s_n$ तथा $d_{n+1} = 2d_n$ को संतुष्ट करते हैं, इसलिए $s_n = 4^n s_0$ , $d_n = 2^n d_0$ और

u_n = \frac{4^n(u_0+v_0) + 2^n(u_0-v_0)}{2}, \qquad v_n = \frac{4^n(u_0+v_0) - 2^n(u_0-v_0)}{2}.

(पर्दे के पीछे: $(1,1)$ और $(1,-1)$ $A$ की अभिलक्षणिक सदिश-दिशाएँ हैं।)

30.3 ग्राफ़ और चालें

परिभाषा 30.11 (ग्राफ़, आसन्नता आव्यूह)

ग्राफ़ में शीर्ष $1, 2, \dots, n$ और शीर्षों के कुछ युग्मों को जोड़ने वाली कोरें होती हैं (दिष्ट ग्राफ़ के लिए क्रमित युग्म)। उसका आसन्नता आव्यूह वह $n \times n$ आव्यूह $M$ है जिसमें $i$ से $j$ तक कोई कोर होने पर $m_{ij} = 1$ और अन्यथा $0$ होता है। $i$ से $j$ तक लंबाई $k$ की चाल $k$ क्रमागत कोरों का ऐसा क्रम है जो $i$ से $j$ तक ले जाए।

M = pmatrix 0 & 1 & 1\\ 0 & 0 & 1\\ 1 & 0 & 0 pmatrix एक दिष्ट ग्राफ़ और उसका आसन्नता आव्यूह (): m_ij = 1 ठीक तब जब i से j तक कोई कोर हो। — $M = \begin{pmatrix} 0 & 1 & 1\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{pmatrix}$ एक दिष्ट ग्राफ़ और उसका आसन्नता आव्यूह (अभ्यास 30.6): $m_{ij} = 1$ ठीक तब जब $i$ से $j$ तक कोई कोर हो।

प्रमेय 30.12 (चालें गिनना)

शीर्ष $i$ से शीर्ष $j$ तक लंबाई $k$ की चालों की संख्या $M^k$ की $(i,j)$ प्रविष्टि है।

उपपत्ति. $k$ पर आगमन। $k = 1$ के लिए यह $M$ की परिभाषा ही है। मान लीजिए दावा $k$ के लिए सही है। $i$ से $j$ तक लंबाई $k+1$ की चाल $i$ से किसी शीर्ष $l$ तक लंबाई $k$ की चाल है, और उसके बाद $l$ से $j$ तक एक कोर; योग और गुणन के सिद्धांतों से उनकी संख्या है

\sum_{l=1}^{n} \bigl(M^k\bigr)_{il}\, m_{lj} = \bigl(M^{k+1}\bigr)_{ij}. \qedhere

∎

उदाहरण 30.13

त्रिभुज ग्राफ़ ( $3$ शीर्ष, सभी युग्म जुड़े हुए) के लिए $M = \begin{pmatrix} 0&1&1\\ 1&0&1\\ 1&1&0\end{pmatrix}$ और $M^2 = \begin{pmatrix} 2&1&1\\ 1&2&1\\ 1&1&2\end{pmatrix}$ : हर शीर्ष से अपने ही पास लौटने वाली लंबाई $2$ की $2$ चालें हैं (किसी भी पड़ोसी से होकर) और हर दूसरे शीर्ष तक $1$ ।

30.4 अभ्यास

अभ्यास 30.1 ★

मान लीजिए $A = \begin{pmatrix} 1 & 2\\ 0 & 1 \end{pmatrix}$ और $B = \begin{pmatrix} 2 & 0\\ 1 & 1 \end{pmatrix}$ हैं। $A + B$ , $AB$ , $BA$ और $A^2$ निकालिए।

हल

हल — अभ्यास 30.1.

A + B = \begin{pmatrix} 3 & 2\\ 1 & 2\end{pmatrix}, \quad AB = \begin{pmatrix} 4 & 2\\ 1 & 1\end{pmatrix}, \quad BA = \begin{pmatrix} 2 & 4\\ 1 & 3\end{pmatrix}, \quad A^2 = \begin{pmatrix} 1 & 4\\ 0 & 1\end{pmatrix}.

ध्यान दीजिए कि $AB \neq BA$ ।

अभ्यास 30.2 ★

बताइए कि निम्नलिखित आव्यूह प्रतिलोमनीय हैं या नहीं, और जहाँ प्रतिलोम हों वहाँ उन्हें निकालिए:

A = \begin{pmatrix} 2 & 5\\ 1 & 3\end{pmatrix}, \qquad B = \begin{pmatrix} 3 & 6\\ 2 & 4\end{pmatrix}.

हल

हल — अभ्यास 30.2.

$\det A = 6 - 5 = 1 \neq 0$ : $A^{-1} = \begin{pmatrix} 3 & -5\\ -1 & 2 \end{pmatrix}$ । $\det B = 12 - 12 = 0$ : $B$ प्रतिलोमनीय नहीं है।

अभ्यास 30.3 ★

आव्यूह-प्रतिलोमन से निकाय $\begin{cases} 2x + 5y = 1\\ x + 3y = 2 . \end{cases}$ हल कीजिए।

हल

हल — अभ्यास 30.3.

निकाय $AX = Y$ है, जहाँ $A$ अभ्यास 30.2 जैसा है और $Y = \begin{pmatrix} 1\\ 2\end{pmatrix}$ :

X = A^{-1}Y = \begin{pmatrix} 3 & -5\\ -1 & 2\end{pmatrix} \begin{pmatrix} 1\\ 2\end{pmatrix} = \begin{pmatrix} -7\\ 3\end{pmatrix}: \qquad x = -7,\ y = 3 .

अभ्यास 30.4 ★★

मान लीजिए $N = \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}$ के साथ $A = \begin{pmatrix} 2 & 1\\ 0 & 2\end{pmatrix} = 2I + N$ है।

जाँचिए कि $N^2 = 0$ , और यह भी कि $I$ तथा $N$ क्रमविनिमेय हैं।
सभी $k \in \N$ के लिए $A^k$ निकालिए और $k=2$ का सूत्र सीधी गणना से सत्यापित कीजिए।

हल

हल — अभ्यास 30.4.

1. $N^2 = \begin{pmatrix} 0&1\\0&0\end{pmatrix} \begin{pmatrix} 0&1\\0&0\end{pmatrix} = 0$ , और $I$ हर आव्यूह के साथ क्रमविनिमेय है।

2. चूँकि दोनों पद क्रमविनिमेय हैं, इसलिए द्विपद प्रमेय लागू होती है और $N^2$ वाले सभी पद लुप्त हो जाते हैं:

A^k = (2I + N)^k = 2^k I + k\,2^{k-1} N = \begin{pmatrix} 2^k & k\,2^{k-1}\\ 0 & 2^k \end{pmatrix}.

$k = 2$ के लिए जाँच: $A^2 = \begin{pmatrix} 2&1\\0&2\end{pmatrix}^2 = \begin{pmatrix} 4&4\\0&4\end{pmatrix}$ , और सूत्र $2^2 = 4$ , $2 \times 2 = 4$ देता है। ✓

अभ्यास 30.5 ★★

मान लीजिए $A = \begin{pmatrix} 0 & 1\\ 1 & 1\end{pmatrix}$ है और $F_n$ फिबोनाच्ची अनुक्रम ( $F_0 = 0$ , $F_1 = 1$ , $F_{n+2} = F_{n+1} + F_n$ )। आगमन से दिखाइए कि $n \geq 1$ के लिए

A^n = \begin{pmatrix} F_{n-1} & F_n\\ F_n & F_{n+1}\end{pmatrix},

और सर्वसमिका $F_{n+1}F_{n-1} - F_n^2 = (-1)^n$ निकालिए। (संकेत: सारणिक गुणा होते हैं: $\det(MN) = \det M \det N$ , जिसे आप $2\times2$ आव्यूहों के लिए जाँच सकते हैं।)

हल

हल — अभ्यास 30.5.

आगमन: $n = 1$ के लिए: $A^1 = \begin{pmatrix} 0&1\\1&1\end{pmatrix} = \begin{pmatrix} F_0 & F_1\\ F_1 & F_2\end{pmatrix}$ । मान लीजिए सूत्र $n$ के लिए सही है; तब

A^{n+1} = A^n A = \begin{pmatrix} F_{n-1} & F_n\\ F_n & F_{n+1}\end{pmatrix} \begin{pmatrix} 0 & 1\\ 1 & 1\end{pmatrix} = \begin{pmatrix} F_n & F_{n-1} + F_n\\ F_{n+1} & F_n + F_{n+1}\end{pmatrix} = \begin{pmatrix} F_n & F_{n+1}\\ F_{n+1} & F_{n+2}\end{pmatrix}.

सर्वसमिका: $2\times2$ आव्यूहों के लिए प्रसार करने पर $\det(MN) = \det M \det N$ दिखता है; अतः $\det(A^n) = (\det A)^n = (-1)^n$ , और $\det A^n = F_{n-1}F_{n+1} - F_n^2$ । (यही कासीनी सर्वसमिका है।)

अभ्यास 30.6 ★★

शीर्षों $\{1, 2, 3\}$ वाले किसी दिष्ट ग्राफ़ में कोरें $1\to2$ , $2\to3$ , $3\to1$ और $1\to3$ हैं।

आसन्नता आव्यूह $M$ लिखिए और $M^2$ तथा $M^3$ निकालिए।
$1$ से $1$ तक लंबाई $3$ की कितनी चालें हैं? उन्हें गिनाइए।

हल

हल — अभ्यास 30.6.

1. शीर्षों को $1, 2, 3$ क्रम में रखने पर:

M = \begin{pmatrix} 0&1&1\\ 0&0&1\\ 1&0&0\end{pmatrix}, \quad M^2 = \begin{pmatrix} 1&0&1\\ 1&0&0\\ 0&1&1\end{pmatrix}, \quad M^3 = \begin{pmatrix} 1&1&1\\ 1&0&1\\ 1&0&1 \end{pmatrix}.

2. $\bigl(M^3\bigr)_{11} = 1$ : शीर्ष $1$ पर लंबाई $3$ की ठीक एक बंद चाल है, अर्थात् $1 \to 2 \to 3 \to 1$ । (चाल $1 \to 3 \to 1$ केवल लंबाई $2$ की है, और $1 \to 3$ फिर $3\to1$ फिर $1\to3$ $3$ पर समाप्त होती है।)

अभ्यास 30.7 ★★

कोई कार-साझा कंपनी दो नगरों $A$ और $B$ के बीच वाहन घुमाती है। हर सप्ताह $A$ की $80\%$ कारें $A$ में ही रहती हैं और $20\%$ $B$ चली जाती हैं; $B$ की $30\%$ कारें $A$ चली जाती हैं और $70\%$ वहीं रहती हैं। मान लीजिए $a_n, b_n$ हर नगर में बेड़े के अनुपात हैं।

$X_n = \begin{pmatrix} a_n\\ b_n\end{pmatrix}$ के साथ $X_{n+1} = MX_n$ लिखिए और $M$ पहचानिए।
साम्य अनुपात ज्ञात कीजिए ( $a + b = 1$ के साथ $MX = X$ हल कीजिए)।
दिखाइए कि $c_n = a_n - 0.6$ $c_{n+1} = 0.5\,c_n$ को संतुष्ट करता है, और निष्कर्ष निकालिए कि बेड़े का बँटवारा साम्य पर अभिसरित होता है।

हल

हल — अभ्यास 30.7.

1. $a_{n+1} = 0.8a_n + 0.3b_n$ , $b_{n+1} = 0.2a_n + 0.7b_n$ : $M = \begin{pmatrix} 0.8 & 0.3\\ 0.2 & 0.7\end{pmatrix}$ ।

2. $MX = X$ से $0.8a + 0.3b = a$ मिलता है, अर्थात् $0.3b = 0.2a$ , इसलिए $b = \frac23 a$ ; और $a + b = 1$ के साथ: $a = 0.6$ , $b = 0.4$ ।

3. $b_n = 1 - a_n$ का उपयोग करने पर: $a_{n+1} = 0.8a_n + 0.3(1 - a_n) = 0.5a_n + 0.3$ , इसलिए

c_{n+1} = a_{n+1} - 0.6 = 0.5a_n + 0.3 - 0.6 = 0.5(a_n - 0.6) = 0.5\,c_n .

अतः $c_n = 0.5^n c_0 \to 0$ : आरंभिक बँटवारा चाहे जो हो, $a_n \to 0.6$ और $b_n \to 0.4$ ।

अभ्यास 30.8 ★★★

मान लीजिए $A = \begin{pmatrix} 3 & 1\\ 1 & 3 \end{pmatrix}$ , $P = \begin{pmatrix} 1 & 1\\ 1 & -1 \end{pmatrix}$ हैं।

$P^{-1}$ निकालिए, फिर $D = P^{-1}AP$ , और जाँचिए कि $D$ विकर्ण है।
$A^n$ का बंद सूत्र निकालिए और उदाहरण 30.10 से तुलना कीजिए।

हल

हल — अभ्यास 30.8.

1. $\det P = -2$ , इसलिए $P^{-1} = -\frac12\begin{pmatrix} -1 & -1\\ -1 & 1\end{pmatrix} = \frac12\begin{pmatrix} 1 & 1\\ 1 & -1\end{pmatrix}$ । तब

AP = \begin{pmatrix} 4 & 2\\ 4 & -2 \end{pmatrix}, \qquad D = P^{-1}AP = \frac12\begin{pmatrix} 1&1\\1&-1\end{pmatrix} \begin{pmatrix} 4&2\\4&-2\end{pmatrix} = \begin{pmatrix} 4 & 0\\ 0 & 2\end{pmatrix}.

2. $A = PDP^{-1}$ से तत्काल आगमन $D^n = \begin{pmatrix} 4^n & 0\\ 0 & 2^n\end{pmatrix}$ वाला $A^n = PD^nP^{-1}$ देता है, इसलिए

A^n = P D^n P^{-1} = \begin{pmatrix} 4^n & 2^n\\ 4^n & -2^n\end{pmatrix}\cdot \frac12\begin{pmatrix} 1&1\\1&-1\end{pmatrix} = \frac12\begin{pmatrix} 4^n + 2^n & 4^n - 2^n\\ 4^n - 2^n & 4^n + 2^n\end{pmatrix}.

$X_0 = \begin{pmatrix} u_0\\v_0\end{pmatrix}$ पर $A^n$ लगाने से ठीक उदाहरण 30.10 के सूत्र फिर मिल जाते हैं।

30.5 समस्या: वह आव्यूह जो फिबोनाच्ची (और मौसम) जानता है

समस्या 30.1

सप्ताहांत समस्या — एक $2 \times 2$ आव्यूह पूरा फिबोनाच्ची उठाए रहता है, एक मार्कोव आव्यूह दीर्घ काल का मौसम बता देता है, और एक अभिलक्षणिक सदिश अरबों का मोल रखता है

आव्यूह एक ऐसी मशीन है जो कोई अवस्था खाती है और अगली लौटा देती है — और इसलिए उसकी घातें पूरे-पूरे भविष्य समेटे रहती हैं। यह समस्या उस चकित कर देने वाले आव्यूह से शुरू होती है जिसकी घातें फिबोनाच्ची संख्याएँ गिना देती हैं (और उनकी सर्वसमिकाएँ एक-एक पंक्ति में सिद्ध कर देती हैं), फिर मौसम को मार्कोव शृंखला के रूप में उसकी स्थायी अवस्था तक चलाती है, और उस अभिलक्षणिक सदिश पर समाप्त होती है जिस पर एक खोज-इंजन खड़ा किया गया था (प्रमेय 30.12, विधि 30.9)।

भाग I — प्रवाह।

$A = \begin{pmatrix} 1 & 2\\ 3 & 4\end{pmatrix}$ और $B = \begin{pmatrix} 0 & 1\\ 1 & 0\end{pmatrix}$ के साथ: $AB$ और $BA$ निकालिए। क्रमविनिमेयता पर क्या फ़ैसला है?
$\begin{pmatrix} 2 & 1\\ 5 & 3\end{pmatrix}$ का प्रतिलोम (प्रतिज्ञप्ति 30.6) निकालिए और उससे $2x + y = 4$ , $5x + 3y = 7$ हल कीजिए।
मान लीजिए $N = \begin{pmatrix} 0 & 1\\ 0 & 0\end{pmatrix}$ है: $N^2$ निकालिए, और हर $n$ के लिए $(I + N)^n = I + nN$ निकालिए।
त्रिभुज ग्राफ़ (तीन शीर्ष, सभी युग्म जुड़े): उसका आसन्नता आव्यूह $A$ लिखिए, $A^3$ निकालिए, और विकर्ण की प्रविष्टियों की व्याख्या कीजिए (प्रमेय 30.12)।
$D = \begin{pmatrix} 2 & 0\\ 0 & \frac12 \end{pmatrix}$ के लिए: $D^n$ और $n \to \infty$ पर उसका व्यवहार बताइए।

भाग II — फिबोनाच्ची आव्यूह। मान लीजिए $F = \begin{pmatrix} 1 & 1\\ 1 & 0\end{pmatrix}$ है और $F_1 = F_2 = 1, F_3 = 2, \dots$ समस्या 13.1 की फिबोनाच्ची संख्याएँ हैं।

$F^2$ , $F^3$ , $F^4$ निकालिए और फिबोनाच्ची संख्याओं के पदों में $F^n$ के व्यापक रूप का अनुमान लगाइए।
अनुमान $F^n = \begin{pmatrix} F_{n+1} & F_n\\ F_n & F_{n-1} \end{pmatrix}$ आगमन से सिद्ध कीजिए।
दोनों पक्षों के सारणिक लीजिए (गुणनफल का सारणिक सारणिकों का गुणनफल है — यदि आपने यह पहले न देखा हो तो $2 \times 2$ आव्यूहों पर जाँच लीजिए): और कासीनी सर्वसमिका $F_{n+1}F_{n-1} - F_n^2 = (-1)^n$ निकालिए — वही “ग़ायब वर्ग” का इंजन, अब एक पंक्ति में सिद्ध।
$F^{m+n} = F^m F^n$ से ऊपर-दाईं प्रविष्टियाँ पढ़िए और योग सूत्र

$F_{m+n} = F_{m+1} F_n + F_m F_{n-1} .$

निकालिए। $m = n = 3$ के लिए उसकी जाँच कीजिए।
योग सूत्र से ( $k$ पर आगमन द्वारा) निकालिए कि $F_n$ $F_{kn}$ को विभाजित करता है, और $F_3 \mid F_6$ तथा $F_3 \mid F_9$ पर उसकी पुष्टि कीजिए।
$F_{100}$ निकालने के लिए $100$ आव्यूह गुणा करने की आवश्यकता नहीं: बार-बार वर्ग कीजिए ( $F^2, F^4, F^8, \dots$ ) और जोड़ते जाइए। कितने आव्यूह-गुणन पर्याप्त हैं, और माध्यमिक विद्यालय खंड की कौन-सी प्राचीन गुणन-तरकीब यही है, अब आव्यूहों तक पदोन्नत?

भाग III — मौसम की मशीन। किसी नगर में: धूप वाले दिन के बाद अगला दिन प्रायिकता $0.8$ से धूप वाला होता है; वर्षा वाले दिन के बाद प्रायिकता $0.4$ से धूप वाला। दिन के बंटन को स्तंभ $\binom{p_{\text{धूप}}}{p_{\text{वर्षा}}}$ के रूप में और विकास को

M = \begin{pmatrix} 0.8 & 0.4\\ 0.2 & 0.6 \end{pmatrix}.

से लिखिए।

जाँचिए कि $M$ के हर स्तंभ का योग $1$ है, और बताइए कि किसी भी मौसम-मशीन में यह गुण क्यों होना ही चाहिए।
आज धूप है। कल और परसों का पूर्वानुमान निकालिए।
स्थायी अवस्था ज्ञात कीजिए: वह बंटन $v$ जिसके लिए $Mv = v$ हो (और जिसकी प्रविष्टियों का योग $1$ हो)। दीर्घ काल में कितने अंश दिन धूप वाले होते हैं?
वर्षा वाले दिन $\binom01$ से शुरू कीजिए और $M$ चार बार लगाइए, और हर क़दम पर स्थायी अवस्था से दूरी दर्ज कीजिए। प्रति क़दम अंतर कितने गुना सिकुड़ता है — और यह किस प्रकार का अभिसरण है?
लघुरूप में पेजरैंक: तीन पृष्ठ, जिनकी कड़ियाँ $A \to B$ , $A \to C$ , $B \to C$ , $C \to A$ हैं। कोई यादृच्छिक पाठक बाहर जाने वाली किसी कड़ी को एकसमान यादृच्छिक ढंग से पकड़ता है। संक्रमण आव्यूह लिखिए, स्थायी अवस्था ज्ञात कीजिए, और पृष्ठों की श्रेणी बनाइए।
श्रेणी की व्याख्या कीजिए: कम पृष्ठों से कड़ियाँ पाने के बावजूद $C$ $A$ जितना ऊँचा अंक क्यों पाता है — स्थायी अवस्था असल में क्या नापती है? (असली पेजरैंक बंद गलियों और छलाँगों के लिए एक अवमंदन गुणक जोड़ता है; अभिलक्षणिक सदिश वाला विचार ठीक यही है।)

भाग IV — विकर्ण का लाभांश।

दो युग्मित राशियाँ $u_{n+1} = 3u_n + v_n$ , $v_{n+1} = u_n + 3v_n$ मानती हैं, अर्थात् अभ्यास 30.8 का आव्यूह $A$ । उसी अभ्यास के विकर्णीकरण ( $D = \operatorname{diag}(4, 2)$ ) का उपयोग करके $u_0 = 1$ , $v_0 = 0$ होने पर $u_n$ का बंद सूत्र दीजिए, और $n = 1, 2, 3$ के लिए उसे सीधी गणना से जाँचिए।
एक-दो वाक्यों में: विकर्णीकरण किसी युग्मित तंत्र के साथ करता क्या है — और प्रश्न 14 की मार्कोव स्थायी अवस्था भी किस अर्थ में अभिलक्षणिक सदिश की ही कहानी है?
समापन — इस सप्ताहांत आव्यूह के तीन चेहरे: बही-खाता (निकाय और प्रतिलोम), क्रमचय-संचय (घातों से गिनी गई चालें और कड़ियाँ), और विकास (फिबोनाच्ची, मौसम, जाल — अभिलक्षणिक दिशाओं से पढ़े गए भविष्य)। हर एक पर एक वाक्य, और आगे का संकेत: स्नातक खंडों का रैखिक बीजगणित इनमें से हर चेहरे को एक पूरा सिद्धांत बना देता है।

हल

हल — समस्या 30.1.

1. $AB = \begin{pmatrix} 2 & 1\\ 4 & 3\end{pmatrix}$ और $BA = \begin{pmatrix} 3 & 4\\ 1 & 2\end{pmatrix}$ : आव्यूहों का गुणन क्रमविनिमेय नहीं है — $B$ दाईं ओर से स्तंभ बदलता है और बाईं ओर से पंक्तियाँ।

2. सारणिक $6 - 5 = 1$ : प्रतिलोम $\begin{pmatrix} 3 & -1\\ -5 & 2\end{pmatrix}$ । उसे $\binom{4}{7}$ पर लगाने पर: $x = 12 - 7 = 5$ , $y = -20 + 14 = -6$ ।

3. $N^2 = 0$ । फिर आगमन से $(I + N)^n = I + nN$ : $(I + nN)(I + N) = I + (n+1)N + nN^2 = I + (n+1)N$ ।

4. $A = \begin{pmatrix} 0&1&1\\ 1&0&1\\ 1&1&0 \end{pmatrix}$ , और $A^3$ की विकर्ण प्रविष्टियाँ $2$ हैं: हर शीर्ष से लंबाई $3$ की ठीक दो बंद चालें (त्रिभुज दक्षिणावर्त या वामावर्त चला हुआ) — गिनती वाली प्रमेय काम पर।

5. $D^n = \begin{pmatrix} 2^n & 0\\ 0 & 2^{-n} \end{pmatrix}$ : एक दिशा फट पड़ती है, दूसरी मर जाती है — विकर्ण की नियतियाँ स्वतंत्र गुणोत्तर अनुक्रम हैं।

6. $F^2 = \begin{pmatrix} 2 & 1\\ 1 & 1\end{pmatrix}$ , $F^3 = \begin{pmatrix} 3 & 2\\ 2 & 1\end{pmatrix}$ , $F^4 = \begin{pmatrix} 5 & 3\\ 3 & 2\end{pmatrix}$ : हर जगह फिबोनाच्ची; अनुमान वैसा ही जैसा बताया गया।

7. यदि $F^n = \begin{pmatrix} F_{n+1} & F_n\\ F_n & F_{n-1}\end{pmatrix}$ हो, तो

F^{n+1} = F^n F = \begin{pmatrix} F_{n+1} + F_n & F_{n+1}\\ F_n + F_{n-1} & F_n \end{pmatrix} = \begin{pmatrix} F_{n+2} & F_{n+1}\\ F_{n+1} & F_n \end{pmatrix} :

वंशानुगति; और आधार-स्थिति $n = 1$ स्वयं $F$ है, जिसमें परिपाटी $F_0 = 0$ का उपयोग होता है (जो पुनरावृत्ति को पीछे की ओर भी बढ़ा देती है)।

8. $\det F = -1$ , इसलिए $\det(F^n) = (\det F)^n = (-1)^n$ ; और सीधे $\det(F^n) = F_{n+1}F_{n-1} - F_n^2$ : कासीनी, एक पंक्ति में। ( $2 \times 2$ सारणिकों के लिए गुणनफल का नियम पाँच मिनट का सुखद प्रसार है।)

9. $F^m F^n$ की ऊपर-दाईं प्रविष्टि: $F_{m+1}F_n + F_m F_{n-1}$ ; $F^{m+n}$ की ऊपर-दाईं: $F_{m+n}$ । $m = n = 3$ के लिए: $F_4 F_3 + F_3 F_2 = 3 \times 2 + 2 \times 1 = 8 = F_6$ ।

10. $k = 1$ के लिए: तुच्छ। यदि $F_n \mid F_{kn}$ हो, तो $m = kn$ के साथ योग सूत्र: $F_{(k+1)n} = F_{kn+1}F_n + F_{kn}F_{n-1}$ : दोनों पद $F_n$ के गुणज हैं। इसलिए सभी $k$ के लिए $F_n \mid F_{kn}$ : जाँचिए कि $F_3 = 2$ $F_6 = 8$ और $F_9 = 34$ को विभाजित करता है।

11. $F^{100} = F^{64} F^{32} F^4$ : सात बार वर्ग ( $F^2, F^4, \dots, F^{64}$ ) और दो बार जोड़-मिलान — यानी निन्यानबे के बदले नौ गुणन। यह मिस्र के लिपिकों की दुगुना करने वाली सारणी की तरकीब ही है, जो संख्याओं से उठकर आव्यूहों पर आ गई: $100$ को द्विआधारी में लिखिए और जिन दुगुनों की ज़रूरत हो उन्हीं को गुणा कीजिए।

12. $0.8 + 0.2 = 1$ और $0.4 + 0.6 = 1$ : कल कोई न कोई मौसम होगा ही — हर स्तंभ एक पूरा प्रायिकता बंटन है, इसलिए प्रायिकता संरक्षित रहती है।

13. कल: $\binom{0.8}{0.2}$ । परसों: $M\binom{0.8}{0.2} = \binom{0.72}{0.28}$ ।

14. $v = \binom{s}{r}$ , $s + r = 1$ के साथ $Mv = v$ : $0.8s + 0.4r = s$ से $0.4r = 0.2s$ , $s = 2r$ मिलते हैं: $v = \binom{2/3}{1/3}$ । दीर्घ काल में तीन में से दो दिन धूप वाले होते हैं — आज चाहे जैसा दिखे।

15. $\binom01$ से: धूप वाले घटक $0.4$ , $0.56$ , $0.624$ , $0.6496$ ; और $\frac23$ से अंतर: $0.267$ , $0.107$ , $0.043$ , $0.017$ — हर क़दम अंतर को ठीक $0.4$ गुना कर देता है (मशीन का दूसरा अभिलक्षणिक मान): स्थायी अवस्था पर गुणोत्तर अभिसरण।

16. स्तंभ ( $A$ , $B$ , $C$ से): $P = \begin{pmatrix} 0 & 0 & 1\\ \frac12 & 0 & 0\\ \frac12 & 1 & 0\end{pmatrix}$ । स्थायी अवस्था: $v_A = v_C$ , $v_B = \frac{v_A}{2}$ , $v_C = \frac{v_A}{2} + v_B$ ; और योग $1$ होने पर: $v = \left(\frac25, \frac15, \frac25\right)$ । श्रेणी: $A$ तथा $C$ पहले स्थान पर बराबरी में, और $B$ अंत में।

17. $C$ $B$ का सारा आवागमन और $A$ का आधा पाता है, और वह सब कुछ $A$ को लौटा देता है: स्थायी अवस्था यह नापती है कि पाठक समय कहाँ बिताता है, न कि उसकी ओर कितनी कड़ियाँ आती हैं — किसी लोकप्रिय पृष्ठ से आई एक कड़ी उजाड़ पृष्ठों की कई कड़ियों पर भारी पड़ती है। यही पुनरावर्ती भारण उस खोज-इंजन का संस्थापक विचार है; और अवमंदन मकड़-जालों तथा बंद गलियों को सँभालता है।

18. $A^n = P D^n P^{-1}$ से $u_n = \frac{4^n + 2^n}{2}$ मिलता है (और $v_n = \frac{4^n - 2^n}{2}$ )। जाँच: $u_1 = 3$ , $u_2 = 10$ , $u_3 = 36$ ; सीधे: $(1,0) \to (3,1) \to (10,6) \to (36, 28)$ : मेल।

19. विकर्णीकरण ऐसे निर्देशांकों पर ले जाता है जिनमें युग्मित तंत्र टूटकर स्वतंत्र गुणोत्तर अनुक्रमों में बिखर जाता है — हर अभिलक्षणिक मान अपनी दौड़ अलग दौड़ता है। मार्कोव की स्थायी अवस्था अभिलक्षणिक मान $1$ का अभिलक्षणिक सदिश है, और प्रश्न 15 की अभिसरण-दर अगला अभिलक्षणिक मान: मौसम की मशीन शुरू से ही अभिलक्षणिक कहानी थी।

20. बही-खाता: कोई निकाय एक ही आव्यूह-समीकरण है, जो एक ही प्रतिलोम से हल हो जाता है। क्रमचय-संचय: आसन्नता आव्यूह की घातें चालें, कड़ियाँ और संबंध गिन देती हैं। विकास: मशीन की घातें अवस्थाओं को उनकी नियतियों तक ले जाती हैं, और अभिलक्षणिक दिशाएँ (फिबोनाच्ची की स्वर्ण दिशा, मौसम की स्थायी अवस्था, जाल का श्रेणी-सदिश) ही वे नियतियाँ हैं। स्नातक खंडों का रैखिक बीजगणित ठीक इसी का विज्ञान है।