Applications of Linear Algebra in Computer Science

MALACS: Applications of Linear Algebra in Computer Science

MALACS.A: Functions and Linear Equations

MALACS.B: Python Programming

MALACS.C: The Complex Field

MALACS.D: The Vector

MALACS.E: Vector Spaces

MALACS.F: Matrices

MALACS.G: The Basis and Dimension

MALACS.H: Gaussian Elimination

MALACS.I: Orthogonalization

MALACS.J: Special Bases

MALACS.K: The Eigenvalue/Eigenvector

MALACS.L: Linear Programming

MALACS.A.1: review function notation, domain/co-domain, identity/associativity, inverse/invertibility connecting to the computer science concept of perfect secrecy (i.e., encryption)

MALACS.A.2: review Python psuedo random number generation, calculating probability distribution and interpreting probability events through application of Caesar's Cypher and other examples of cryptosystems

MALACS.B.3: utilize sets, lists, dictionaries, comprehensions, indexing, and tuples in Python

MALACS.B.4: understand how to program and utilize modules and control statements (e.g., loops, conditionals, grouping) in Python

MALACS.B.5: program input and output features to read from and write to files in Python

MALACS.C.6: perform operations of complex number numbers (e.g., absolute value, adding, multiplying) and understand how they produce different transformations

MALACS.C.7: understand how complex numbers connect to the unit circle and represent them in polar form; perform transformations in polar form and utilize Euler's formula/The First Law of Exponentiation to understand these transformations; connect to performing image transformation on a computer graphic program

MALACS.C.8: work with the Galois Field to understand further concepts in perfect secrecy and network coding (i.e., providing efficiency in streaming services)

MALACS.D.9: perform vector operations in R(n) including addition, scalar multiplication, and dot product; review concepts of convex and affine combinations; represent and perform these operations using dictionaries and the Vec.py class in Python

MALACS.D.10: find the distance, its unit vector in the same or opposite direction, the projection of a vector onto a given vector or vector space, dot product, inner product, cross product, and angle between two vectors in Euclidean space

MALACS.D.11: connect use of vectors in Galois Field(2) by applying concepts of perfect secrecy, all-or-nothing secret sharing, and programming/solving lights out games

MALACS.D.12: use the dot product to display the concept of simple authentication schemes and interacting with them, and performing a senator voting record analysis

MALACS.D.13: solve triangular systems of linear equations using upper-triangular systems, backward substitution, and other algorithms

MALACS.E.14: define and discuss uses of linear combinations and understand how to solve for coefficients or linear combinations, connect to programmed/solved lights out game

MALACS.E.15: define span and what it means for linear combinations to be a span of vectors; connect span to simple authentication schemes; understand the geometric depiction of the span of vectors over R and the geometry of solution sets of homogenous linear equations and systems; understand the geometric interpretations of R^2 and R^3

MALACS.E.16: determine if a given set of vectors in a vector space is a spanning set for that vector space and if they are linearly independent

MALACS.E.17: determine whether a provided subset of a vector space is a subspace and find the dimension of a subspace

MALACS.E.18: find whether a vector is a linear combination of a given finite set of vectors in a vector space and provide this linear combination

MALACS.E.19: determine if a linear combination is an affine combination and determine if an affine space exists by translating a vector space, represent and affine space as a solution set to a linear system

MALACS.F.20: review the structure of a matrix and composition of the identity matrix, determine the size, transpose, inverse, rank, and LU-factorization of a matrix; interpret matrices as vectors

MALACS.F.21: generate an augmented coefficient matrix from a system of linear equations

MALACS.F.22: perform matrix operations including transpose, addition, scaler multiplication, dot product, and multiplication; compute the inner and outer product

MALACS.F.23: define and understand what the null space is by connecting to concepts of homogenous linear systems/matrix equations, and error correcting codes such as linear codes and Hamming's code

MALACS.F.24: factor a given matrix into the product of two elementary matrices, find the adjoint of a matrix and use it to find the inverse of the matrix (understanding the conditions for invertibility) or solve a system of linear equations

MALACS.F.25: program error correcting code concepts such as Hamming's code using matrix operations

MALACS.F.26: program transformations in 2D geometry using Python and concepts of matrix operations

MALACS.G.27: define the coordinate representation of a basis and connect to lossy compression in computer science; find a basis for the column or row space of a matrix, and find a basis for and the dimension of the nullspace of a matrix

MALACS.G.28: review the minimum spanning forest problem in GF(2) in connection with the Grow and Shrink Algorithms and how to formulate the problem in linear algebra

MALACS.G.29: define what it means for vectors to be linearly dependent and linearly independent and define the Superfluous-Vector Lemma; perform tests of linear dependence

MALACS.G.30: demonstrate that every vector space has a basis and any finite set of vectors contains a basis for its span (e.g., Subset-Basis Lemma)

MALACS.G.31: determine whether a given set of vectors in a vector space forms a basis for that vector space and recognize standards bases in the vector spaces nth dimensional Euclidean space, the set of all polynomials of degree greater than or equal to n

MALACS.G.32: find the transition matrix from one basis to another (i.e., change of basis)

MALACS.G.33: connect the Exchange Lemma to the concept of camera image perspective rendering in a Python lab

MALACS.G.34: define and determine the dimension and rank of a basis (and therefore vector space); use it to prove the Morphing Lemma and prove the Superset-Basis Lemma

MALACS.G.35: discuss rank theorem and demonstrate its use via the Simple Authentication Schema in computer science

MALACS.G.36: utilize direct sum to add vector spaces and find the basis for the direct sum and understand if two subspaces are complementary

MALACS.G.37: understand if a linear function is invertible utilizing the concept of dimension and determine if a function is onto or one-to-one; discuss in connection with Kernal-Image Theorem and Rank-Nullity Theorem, demonstrate using checksums

MALACS.H.38: use elementary row operations to create matrices in row-echelon and reduced row-echelon form

MALACS.H.39: solve systems of linear equations and finding the basis for a Null space by use of Gaussian Elimination, Gauss-Jordan Elimination, LU factorization, and Cramer's Rule; show how the simple authentication scheme can be attacked/improved over GF(2) using Guassian Elimination

MALACS.H.40: understand how Threshold Secret Sharing works in conjunction with Gaussian Elimination through a programming lab in Python

MALACS.H.41: understand how factoring integers can be performed using Euclid's algorithm and utilizing prime set factors in Python

MALACS.I.42: determine if two given vectors/sets of vectors(complements)/subspaces are orthogonal, parallel, or neither; find the orthogonal component of a given subspace

MALACS.I.43: find an orthogonal basis for a given basis/subspace/inner product space by applying the Gram-Schmidt orthonormalization process

MALACS.I.44: given the solution space of a homogenous system of linear equations, find an orthonormal basis

MALACS.I.45: use orthogonalization to find the closest point in the span of many vectors, compute a basis/subset basis, direct sums of complements

MALACS.I.46: define and perform QR factorization of a matrix to compute solutions to the matrix equation Ax=b; use to perform the application of least squares to find the line or curve of best fit (linear/quadratic) to approximate data in the industrial espionage problem/sensor node problem/machine learning problem

MALACS.J.47: utilize compression by suppression to find the closest k-sparse vector coordinate representation in terms of an orthogonal basis

MALACS.J.48: understand how images and sounds can be represented as wavelets and the bases representation of wavelets as well as wavelet transformation, implementation, and decomposition, perform Python lab on using wavelets to perform file compression

MALACS.J.49: define and demonstrate the Fourier transform connecting how a sound is stored as a sequence of amplitude samples and how the Fast Fourier Transform Algorithm is utilized/derived/coded

MALACS.K.50: verify the eigenvalue/eigenvector of a given matrix while understanding the geometric interpretation and coordinate representation; connect to the Internet Worm case of 1988; perform eigen theorem proofs

MALACS.K.51: find the characteristic equation and eigenvalues/corresponding eigenvectors of a given matrix and determine if the matrix is diagonizable/symmetric/orthogonal

MALACS.K.52: find a nonsingular matrix(D) for a given matrix (if one exists) such that D^-1AD is diagonal; find a basis for the domain of a linear transformation such that the matrix of the linear transformation relative to the basis is diagonal

MALACS.K.53: find the eigenvalues of a given symmetric matrix and find the dimension of the corresponding eigenspace

MALACS.K.54: determine an orthogonal matrix that diagonalizes a given matrix

MALACS.K.55: discuss how Markov chains work to model various concepts such as population movement, dance patterns, literary documents, and Google's search engine PageRank

MALACS.K.56: find the determinant, minors, and cofactors of a given matrix and use the determinant to find whether a given matrix is singular/non-singular; use determinant properties to characterize eigenvalues

MALACS.K.57: connect use of the determinant and eigenvectors to code functionality of Google's PageRank search engine in Python

MALACS.K.58: utilize eigenvalues/vectors and single value decomposition to program face recognition software (Eigenfaces)

MALACS.L.59: explore samples of linear programming cases including the diet problem, the vertices of polyhedra (polyhedral combinatorics), the simplex algorithm, game theory, nonzero-sum games, and compressed sensing for MRI imaging

MALACS.L.60: perform a Python lab to explore concepts of linear programming

MALACS.L.61: perform a machine learning lab on a large set of health care data that incorporates concepts of linear programming