Q. No. 01: Write down the application of Linear System of Equations in IT with five examples (3-5 Pages).

Before explaining applications of linear algebra, I first want to explain what Linear Algebra is and then there is system of linear equations in Linear algebra which is my topic.

Linear algebra is a branch of mathematics that deals with the study of linear equations, linear functions, and their representations in vector spaces using matrices. It is a fundamental concept in mathematics, physics, engineering, and computer science, and is used to model and analyze various phenomena.

My task is to explain its application in Information Technology in this specific question. Following are the key applications of linear algebra in IT:

• Computer Networks
• Cryptography
• Web Browsing (Page Rank Algorithm)
• Computer Graphics
• Face Recognition

This was the overview and now we explain each heading in detail with enough examples and theory.

1. Computer Networks

First we see what are computer networks

“A network is a collection of interconnected elements, such as paths, cables and nodes in a computer network”

In network problems, linear algebra can be utilized to model and analyze network flow. The flow of information or data through a network can be represented as a set of linear equations, where each equation represents the flow through a specific element of the network.

1. Traffic Flow

   Linear algebra is applied in the modeling of traffic flow across networks, where data is transmitted through various paths between nodes. The flow of data can be expressed using matrices, and the system of linear equations represents the constraints imposed by bandwidth and capacity of the links.

   • Example: Suppose we have a network where data flows between multiple routers. Linear equations can model the flow between routers, with each equation representing the flow of data along a given path.

     See this example:

     

     It follows from the conversation of flow at node A that:

     $$ x_1 + x_2 = 30 $$

     Similarly, at the other nodes we have

     $$ x_2 + x_3 = 35 \quad (\text{node } B) $$

     $$ x_3 + 15 = 60 \quad (\text{node } C) $$

     $$ x_1 + 15 = 55 \quad (\text{node } D) $$

     These Four conditions produce the linear system

     $$ \begin{aligned} x_1 + x_2 &= 30 \\ x_2 + x_3 &= 35 \\ x_3 &= 45 \\ x_1 &= 40 \end{aligned} $$

We can determine the direction of data flow as well as input and output but remember:

“System of linear Equations is only applicable where data input and output is same.”

2. Cryptography

First we see what is Cryptography

“Cryptography refers to the encryption and decryption of sensitive information derived from mathematical concepts to transform messages in ways that are secure from end to end.”

There are different algorithms or methods for cryptography but I discuss only Hill cipher method, which uses matrix.

Hill Cipher Method: This method uses a matrix as a cipher to encode a message, and it’s extremely difficult to break when a large matrix is used. The receiver of the message decodes it using the inverse of the matrix. This first matrix is called the encoding matrix and its inverse is called the decoding matrix.

See the example here:

$$ A = \begin{bmatrix} 1 & -1 & 0 \\ 1 & 0 & -1 \\ -6 & 2 & 3 \end{bmatrix} \textit{ Message: \textbf{SNITCH}} $$

$$ S = 19, \, N = 14, \, I = 9, \, T = 20, \, C = 3, \, H = 8  $$

$$ \textit{Augmented Matrix} = \left[ 19 \; 14 \; 9 \right], \left[ 9 \; 20 \; 3 \right] $$

$$ \begin{bmatrix} 19 & 14 & 9 \end{bmatrix} \begin{bmatrix} 1 & -1 & 0 \\ 1 & 0 & -1 \\ -6 & 2 & 3 \end{bmatrix}

\begin{bmatrix} -21 & -1 & 13 \end{bmatrix}\\ \begin{bmatrix} 9 & 20 & 3 \end{bmatrix} \begin{bmatrix} 1 & -1 & 0 \\ 1 & 0 & -1 \\ -6 & 2 & 3 \end{bmatrix}

\begin{bmatrix} 11 & -3 & -11 \end{bmatrix}\\ $$

$$ \textit{\textbf{Encrypted Matrix}} = [-21 \; -1 \; 13],\\ [11 \; -3 \; -11] $$

$$ A^{-1} = \begin{bmatrix} -2 & -3 & -1 \\ -3 & -3 & -1 \\ -2 & -4 & -1 \end{bmatrix} \\ \begin{bmatrix} -21 & -1 & 13 \end{bmatrix} \begin{bmatrix} 11 & -3 & -11 \end{bmatrix} \begin{bmatrix} -2 & -3 & -1 \\ -3 & -3 & -1 \\ -2 & -4 & -1 \end{bmatrix} \\= \begin{bmatrix} 19 & 14 & 9 \end{bmatrix} \begin{bmatrix} 9 & 20 & 3 \end{bmatrix} $$

$$ \\\textit{\textbf{Decrypted Matrix}} = [19 \; 14 \; 9], [9 \; 20 \; 3] = [S \; N \; I], [T \; C \; H] = \textbf{SNITCH} $$

3. Web Browsing (Page Rank Algorithm)

First we see what is Page rank algorithm:

“The Page Rank algorithm is a link analysis method used to rank web pages in a hyperlinked document web, such as the World Wide Web”

here is the example of application of linear algebra:

Node 1 has 3 outgoing edges, so it will pass on  of its importance to each of the other 3 nodes. Node 3 has only one outgoing edge, so it will pass on all of its importance to node 1. In general, if a node has k outgoing edges, it will pass on  of its importance to each of the nodes that it links to. Let us better visualize the process by assigning weights to each edge. Let us denote by A the transition matrix of the Graph:

$$ A = \begin{bmatrix} 0 & 0 & \textcolor{red}{1} & \textcolor{green}{\frac{1}{2}} \\ \textcolor{cyan}{1} & 0 & 0 & 0 \\ 0 & \textcolor{cyan}{\frac{1}{2}} & \textcolor{red}{1} & 0 \\ \textcolor{cyan}{\frac{1}{2}} & 0 & 0 & 0 \end{bmatrix}. $$