Linear Algebra In Computing
The need to connect mathematics with the real world leads us to search for applications such as linear algebra to see the reality extracted from theoretical knowledge in day-to-day practices.
Linear algebra is very well applied in the computer world, with its wide number of operations, for example, it is applied in search engine algorithms such as Google, in computer security, cryptography, image management, all this requires the application of vectors and matrices, which is provided by linear algebra, a branch of mathematics very useful for various applications in everyday life.
Linear algebra 1 ‘a branch of mathematics that deals with closed mathematical structures under the operations of addition and scalar multiplication and that includes the theory of systems of linear equations, matrices, determinants, vector spaces, and linear transformations’ has a wide variety of applications in different branches such as administration, economics, engineering, physics, among others.
For its part, computing designates the action and effect of computing, performing a mathematical calculation, refers to technology designed for automatic handling of information through the use of computers, computing is part of science and technology, through the process of analysis and data processing, development and implementation of applications in computer systems.
Computing has a very close relationship with mathematics, it is used in many processes, linear algebra applications in the computer world are used in the development of some applications such as video games, 2D and 3D graphics modeling and designs, in the scale and adjustment of images among others. It is also applied in search engines such as Google, that through vectors, matrices, and mathematical calculations, the search concepts are managed for the results sample. Linear algebra is also applied in computer security in the field of cryptography to transform the text into structures that are difficult to recognize.
Currently, there are Internet search engines that make the collection of information more efficient according to the needs of users. Internet search engines manage a database ordered according to keywords that facilitate access to information.
One of the most successful search engines of our day is Google. The algorithm used to create this search engine is PageRank.
2 ‘PageRank is an algorithm designed by Google to help evaluate the authority of a web page and a website in general’ In the PageRank model, which is based on graph theory, the universe of indexed web pages is a large directed graph, where each census web page is a node, and there will be an arrow from page to page if there is a link from the first page to the second.
In this large directed graph, one now has to assign importance to each page. A reasonable way to assign importance could be that the more links a page receives, the more important it will be. The importance of the page is directly proportional to the sum of the amounts of pages that link to it. This postulate can be translated with the help of linear algebra. The incidence matrix of the graph will be considered, which is defined as the square matrix of size equal to the number of nodes in the graph. In this matrix, we will put a 1 in the place if there is a link from to . If there is not, we will put a zero, for example, the incidence matrix of the graph in Figure 1 is as follows:
This is where linear algebra is reflected along with the vectors and eigenvalues.
The PageRank algorithm is still used today, in addition to this parameter, others such as language models are taken into account, (Google now processes tracked phrases, synonyms or misspelt words) or antiquity or the freshness of the web document (some searches have their best information on the pages that have been created in the last hours).
A popular application is SVD decomposition (singular value decomposition) in which you have a matrix (also seen as a vector space) and you can get a factor representation of this matrix of three matrices:
The singularity is that S is diagonal and gives you the eigenvalues of the matrix, contains the eigenvectors associated with the matrix and = identity matrix.
Apart from the SVD, there is the decomposition QR, ALU, PALU, etc., which are iterative processes with similar characteristics.
As you can see, the linear part is finding the eigenvalues and vectors that generate the space of the original matrix.
It is the incidence matrix of the internet graph, and the import vector, then it is true:
Where is the constant of proportionality?
The vector of the importance of web pages is a positive eigenvector of the matrix and the constant of proportionality is the eigenvalue associated with this vector.
Another example of the application of linear algebra in computing is present when we deal with digital image processing, using linear algebra tools we apply: translation, rotation, skewing, scaling, use of Bézier curves, reflection, and channel adjustments. Brightness and Contrast. Other more complex operations such as filters require the combination of linear algebra with other mathematical tools.
An image can be represented as a matrix, full of small elements known as pixels. By assigning a number to each color, the matrix becomes a numerical matrix. Filters are applied to digital images to improve quality or make information search faster. For example: smoothing the image, reducing the number of intensity variations between each pixel, that is, not abruptly changing color between one cell of the matrix and another. Each operation is performed directly on the values of the matrix. Brightness adjustment involves changing the percentage of luminescence and darkness of a colour
Where:
- corresponds to a vector corresponding to the image.
- is the brightness adjustment parameter, the value of which ranges from −100 to 100.
- Invert Colors (Negative): This operation is about transforming each RGB to its negative.
The rotation of an image is given by a linear transformation in which the coordinates of the image point are expressed in terms of those of the original point through equations:
3“RGB color model is the additive color model using Red, green and blue colors. The main use of the RGB color model is for displaying images in electronic devices”
The RGB color system is used to better understand the algebraic structure and introduce concepts such as the linear combination of vectors, the generator system and the base of a vector space, and the convex envelope of a set of vectors.
In this model, each color is identified with a vector of R3, where each coordinate represents the intensity of the colors red (R), green (G) and blue (B), which varies on a scale from 0 to 255.
The red color is represented by the vector (255, 0, 0), the green by the vector (0, 255, 0) and the blue by the vector (0, 0, 255), obtaining in each case a resulting monochrome color . The absence of color, that is, the color black, is obtained when the three components are 0, obtaining the vector (0, 0, 0). When mixing any pair of primary colors, the secondary additive colors appear: yellow (255, 255, 0), cyan (0, 255, 255) and magenta (255, 0, 255). The white color is formed by mixing the three primary colors (255, 255, 255). In this way, we identify color mixing with vector addition.
If we think of the set of all colors as vectors of R3 of the form (x, y, z) where 0 ≤ x, y, z ≤ 255, we can identify the mixture of colors with the sum of vectors, and the product of a vector by a scalar as the modification of the intensity of the primary colors red, green and blue that make up the color. For example, the dark brown color is identified on the RGB scale with the vector (100, 50, 0). If we multiply it by 1.5 we obtain the vector (150, 75, 0) that is identified with the brown color. However, if we multiply it by 2, we obtain the vector (200, 100, 0) that represents light brown.
References
- Definition of linear algebra: https://www.merriam-webster.com/dictionary/linear%20algebra
- PageRank: https://www.bigcommerce.com/ecommerce-answers/understanding-how-pagerank-works/
- 3RGB model: https://www.educba.com/rgb-color-model/
- PageRank operation: https://www.cs.princeton.edu/~chazelle/courses/BIB/pagerank.htm
- Image processing: https://www.nibcode.com/en/blog/1135/linear-algebra-and-digital-image-processing-part-I
- Matrices and digital images: http://dmuw.zum.de/images/6/6d/Matrix-en.pdf
- RGB model; https://www.geeksforgeeks.org/computer-graphics-the-rgb-color-model/
