Systems of Linear Equations: PageRank, Circuit Analysis, and Matrix Operations

Application of Linear Systems in Circuits and Web Search

• Circuit Analysis Example (Kirchhoff's Laws):

  • A circuit consists of three nodes with voltages $V_1, V_2,$ and $V_3$.

  • Components include resistors of $1\,K\Omega$ and current sources of $1\,mA$.

  • Nodal equations derived from the circuit diagram:

  • Node 1: $-1 + V_1 + (V_1 - V_2) = 0 \rightarrow 2V_1 - V_2 = 1$

  • Node 2: $(V_2 - V_1) + V_2 + (V_2 - V_3) = 0 \rightarrow -V_1 + 3V_2 - V_3 = 0$

  • Node 3: $-1 + V_3 + (V_3 - V_2) = 0 \rightarrow -V_2 + 2V_3 = 1$

  • This results in a system of linear equations with 3 unknowns ($V_1, V_2, V_3$) and 3 equations.

• PageRank Algorithm (Web Search):

  • The Problem: When performing a web search, pages are retrieved based on importance ($x_i$). The page with the maximum $x_i$ value is considered the most important and is shown first.

  • Graph Representation: Webpages are visualized as nodes in a graph, and links between them are directed edges.

  • Condition for Importance ($x_i$): The importance of a page is determined by the importance of the pages linking to it, divided by the number of outgoing links from those source pages.

  • Illustrative System of Importance:

  • $x_0 = \frac{x_3}{3}$ (Page 3 has 3 outgoing links to nodes 0, 1, and 4)

  • $x_1 = x_0 + \frac{x_3}{3}$ (Page 0 has 1 outgoing link to page 1; Page 3 contributes 1/3 of its importance)

  • $x_2 = \frac{x_1}{2}$ (Page 1 has 2 outgoing links to pages 2 and 3)

  • $x_3 = \frac{x_1}{2} + \frac{x_2}{2} + x_4$ (Page 1 contributes 1/2; Page 2 has 2 outgoing links to 3 and 4; Page 4 has 1 outgoing link to 3)

  • $x_4 = \frac{x_2}{2} + \frac{x_3}{3}$ (Page 2 contributes 1/2; Page 3 contributes 1/3)

  • The logic follows: $x_i = \sum \frac{x_j}{\text{number of outgoing links of } j}$, where $j$ links to $i$.

Analysis of Two-Variable Linear Systems

• General Form:

  • $a_1x + b_1y = c_1$

  • $a_2x + b_2y = c_2$

• Three Possible Types of Solutions:

  1. Unique Solution: The two straight lines intersect at exactly one point.

  2. Infinitely Many Solutions: Both lines are identical (coincident).

  3. No Solution: The lines are parallel and do not intersect.

• Graphical Determination (Slope-Intercept View):

  • If $b_1, b_2 \neq 0$, the equations can be rewritten as:

  • $y = (-\frac{a_1}{b_1})x + \frac{c_1}{b_1}$

  • $y = (-\frac{a_2}{b_2})x + \frac{c_2}{b_2}$

  • Let slopes be $m_1 = -\frac{a_1}{b_1}$ and $m_2 = -\frac{a_2}{b_2}$.

  • If $m_1 \neq m_2$, there is a unique solution.

  • If $m_1 = m_2$, the lines are either parallel (no solution) or they coincide (infinite solutions).

• Special Cases for Coefficients:

  • If either $b_j = 0$: One line is vertical ($x = \frac{c_j}{a_j}$).

  • If both $b_1 = 0$ and $b_2 = 0$:

  • Infinite solutions if $\frac{c_1}{a_1} = \frac{c_2}{a_2}$.

  • No solution if $\frac{c_1}{a_1} \neq \frac{c_2}{a_2}$.

Algebraic Methods and Gaussian Elimination

• Triangular Forms:

  • A system is "easy" to solve if it is in a triangular form with a non-zero diagonal (e.g., $a_1 \neq 0, a_2 = 0, b_2 \neq 0$):

  • $a_1x + b_1y = c_1$

  • $b_2y = c_2$

  • Solutions: $y = \frac{c_2}{b_2}$ and $x = \frac{c_1 - b_1(\frac{c_2}{b_2})}{a_1}$.

• Elimination Method:

  • To solve a non-triangular system, eliminate one variable. Replace Equation (2) with $\text{Eq (2)} - (\frac{a_2}{a_1}) \times \text{Eq (1)}$.

  • This transforms the system into:

  • $a_1x + b_1y = c_1$

  • $(b_2 - \frac{a_2b_1}{a_1})y = c_2 - \frac{a_2c_1}{a_1}$

  • Solving for $y$ yields:

  • $y = \frac{a_2c_1 - a_1c_2}{a_2b_1 - a_1b_2}$

Matrix Representation of Linear Systems

• Components:

  • Coefficient Matrix: $\begin{pmatrix} a_1 & b_1 \\ a_2 & b_2 \end{pmatrix}$

  • Variable Vector: $\begin{pmatrix} x \\ y \end{pmatrix}$

  • Constant Vector: $\begin{pmatrix} c_1 \\ c_2 \end{pmatrix}$

  • Augmented Matrix: $\begin{pmatrix} a_1 & b_1 & | & c_1 \\ a_2 & b_2 & | & c_2 \end{pmatrix}$

• Row Operations for Row Echelon Form:

  1. Interchange two rows.

  2. Multiply a row by a non-zero scalar ($R_i \rightarrow tR_i$).

  3. Add a multiple of one row to another row ($R_i \rightarrow R_i + tR_j$).

• Examples of System Solutions via Matrices:

  1. Unique Solution:

  • $x + y = 1$

  • $x + 2y = 3$

  • Augmented Matrix: $\begin{pmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \end{pmatrix}$

  • $R_2 \rightarrow R_2 - R_1 \Rightarrow \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 2 \end{pmatrix}$

  • Result: $y = 2, x = -1$.

  1. Infinite Solutions:

  • $2x + 3y = 5$

  • $4x + 6y = 10$

  • $R_2 \rightarrow R_2 - 2R_1 \Rightarrow \begin{pmatrix} 2 & 3 & 5 \\ 0 & 0 & 0 \end{pmatrix}$

  • Solution: $x = \frac{5 - 3y}{2}$.

  1. No Solution:

  • $2x + 3y = 5$

  • $4x + 6y = 11$

  • $R_2 \rightarrow R_2 - 2R_1 \Rightarrow \begin{pmatrix} 2 & 3 & 5 \\ 0 & 0 & 1 \end{pmatrix}$

  • The equation $0x + 0y = 1$ is a contradiction.

Multi-Equation Systems (3 Equations, 2 Variables)

• System Structure:

  • $a_1x + b_1y = c_1$

  • $a_2x + b_2y = c_2$

  • $a_3x + b_3y = c_3$

• Matrix Approach: Represent as a $3 \times 2$ coefficient matrix multiplied by a $2 \times 1$ variable vector, equated to a $3 \times 1$ constant vector.

• Elimination Strategy:

  • Use $a_1$ as a pivot to make entries in column 1 ($a_2, a_3$) zero.

  • Then use the second row to make the entry in the third row, second column zero.

Problems and Worked Examples

• Unique Solution Condition Problem:

  • System: $x - 3y = 4$ and $3x + ky = -12$.

  • Find $k$ such that there is a unique solution.

  • Matrix representation: $\begin{pmatrix} 1 & -3 & 4 \\ 3 & k & -12 \end{pmatrix}$

  • $R_2 \rightarrow R_2 - 3R_1 \Rightarrow \begin{pmatrix} 1 & -3 & 4 \\ 0 & k+9 & -24 \end{pmatrix}$

  • For a unique solution, the diagonal entry must be non-zero: $k + 9 \neq 0 \rightarrow k \neq -9$.

• Consistency Check Example (No Solution Case):

  • System:

  • $-2x_1 + 3x_2 = 1$

  • $-x_1 + x_2 = 0$

  • $2x_2 = 5$

  • Row operation sequence:

  • $R_2 \rightarrow R_2 - \frac{1}{2}R_1 \Rightarrow \begin{pmatrix} -2 & 3 & 1 \\ 0 & -\frac{1}{2} & -\frac{1}{2} \\ 0 & 2 & 5 \end{pmatrix}$

  • $R_3 \rightarrow R_3 + 4R_2 \Rightarrow \begin{pmatrix} -2 & 3 & 1 \\ 0 & -\frac{1}{2} & -\frac{1}{2} \\ 0 & 0 & 3 \end{pmatrix}$

  • The resulting equation $0x_1 + 0x_2 = 3$ indicates the system has no solution.

• Consistency Check Example (Unique Solution Case):

  • System:

  • $x_1 + x_2 = 1$

  • $x_1 + 2x_2 = 2$

  • $3x_1 + 4x_2 = 4$

  • Row operation sequence:

  • $R_2 \rightarrow R_2 - R_1$

  • $R_3 \rightarrow R_3 - 3R_1$

  • Resulting matrix: $\begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \end{pmatrix}$

  • $R_3 \rightarrow R_3 - R_2 \Rightarrow \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{pmatrix}$

  • This leads to $y = 1$ and $x + 1 = 1 \rightarrow x = 0$. A unique solution exists: $(0, 1)$.