CS6015: Linear Algebra and Random Processes
Course information
When: JulNov 2017
Lectures: Slot B
Where: CS34
Teaching Assistants: Purvi Goel, Ditty Matthew, Hardi Shaileshbhai Shah, Abhishek kumar, Jom Kuriakose
Office Hours:
Instructor  
Prashanth  Wednesday  2:30pm to 3:30pm  BSB 314 
TAs  
Abhishek  Monday  2:30pm to 3:30pm  DON lab 
Hardi  Tuesday  2:30pm to 3:30pm  DON lab 
Ditty  Wednesday  2:30pm to 3:30pm  AIDB lab 
Jom  Thursday  2:30pm to 3:30pm  DON lab 
Purvi  Friday  2:30pm to 3:30pm  DON lab 
Course Content
Linear Algebra
 Matrices
Matrix Multiplication, Transposes, Inverses, Gaussian Elimination, factorization A=LU, rank
 Vector spaces
Column and row spaces, Solving Ax=0 and Ax=b, Independence, basis, dimension, linear transformations
 Orthogonality
Orthogonal vectors and subspaces, projection and least squares, GramSchmidt orthogonalization
 Determinants
Determinant formula, cofactors, inverses and volume
 Eigenvalues and Eigenvectors
Characteristic polynomial, Diagonalization, Hermitian and Unitary matrices, Spectral theorem, Change of basis
 Positive definite matrices and singular value decomposition
Random processes
 Preliminaries
Events, probability, conditional probability, independence, product spaces
 Random Variables
Distributions, law of averages, discrete and continuous r.v.s, random vectors, Monte Carlo simulation
 Discrete Random Variables
Probability mass functions, independence, expectation, conditional expectation, sums of r.v.s
 Continuous Random Variables
Probability density functions, independence, expectation, conditional expectation, functions of r.v.s, sum of r.v.s, multivariate normal distribution, sampling from a distribution
 Convergence of Random Variables
Modes of convergence, BorelCantelli lemmas, laws of large numbers, central limit theorem, tail inequalities
 * Advanced topics (if time permits)
Markov chains, minimum mean squared error estimation
Grading
Midterm (Linear Algebra concepts): 30%
Final exam (Probability concepts): 30%
Quizzes: 20% (Best 5 out of 8)
Programming Assignments: 20%
Target Audience
Masters (M.Tech/M.S.) and Ph.D. students
Important Dates
Problem Sets  Quizzes  Tutorials  MidSem  EndSem 

Aug 7  Aug 16  Aug 11  When: 10am to 12pm, Sep 24 Where: CS34 and CS36  When: 1pm to 4pm, Nov 15 Where: CS34 and CS36 
Aug 18  Aug 28  Sep 1  
Aug 
Sep 5  Sep 20  
Sep 11  Sep 18  Oct 13  
Sep 28  Oct 6  Oct 23  
Oct 10  Oct 17  Nov 10  
Oct 20  Oct 27  
Oct 27  Nov 3 
Problem sets
Quizzes/Exams
Tutorials
Textbooks
Linear algebra and applications by Gilbert Strang
Probability and random processes by Geoffrey Grimmett and David Stirzaker
Additional references:
Linear Algebra: Pure and Applied by Edgar Goodaire
ECE 313 UIUC course lecture notes by Bruce Hajek
Introduction to probability models by Sheldon Ross
Schedule
Part I: Linear Algebra  
Lecture number  Topics Covered  Section reference (Strang's book) 

Lecture 1  Course Organization Motivation for studying linear algebra 

Lecture 2  Geometry of linear equations  row picture, col picture Vector space, subspace  definition, examples Linear combinations, linear independence 
1.2 
Lecture 3  Transpose  properties Inverse Gaussian elimination 
1.3 
Lecture 4  Computational cost of elimination Matrix multiplication  four view GaussJordan method 
1.4 
Lecture 5  Factorization A=LU and A=LDU Row exchanges, permutation matrices Uniqueness of LU/LDU factorization for invertible matrices 
1.5 
Lecture 6  Column and null spaces Null space computation by solving Ax=0 Pivot and free variables, special solutions row reduced echelon form 
2.1, 2.2 
Lecture 7  Dimension = number of vectors in any basis Rank, rowrank = colrank rank + nullity = number of columns 
2.3, 2.4 
Lecture 8  Orthogonal vectors and subspaces Row space orthogonal to null space 
3.1 
Quiz 1  
Lecture 9  Projection onto a line Projection onto a subspace 
3.2 
Lecture 10  Least squares data fitting Orthonormal vectors 
3.3 
Lecture 11  Four fundamental subspaces (again) Least squares data fitting 
2.4, 3.3 
Lecture 12  Orthogonal bases Gram Schmidt algorithm Factorization A=QR 
3.4 
Quiz 2  
Lecture 13 
Linear transformations: definition, matrix representation 
2.6 
Lecture 14 
Composition of linear transformations Change of basis 
Change of basis: Section 46 of Halmos's text 
Lecture 15  Similarity of transformations  Section 47 of Halmos's text 
Quiz 3  
Lecture 16  Determinants: Properties, Formula  4.2, 4.3 
Lecture 17  Determinants: Cofactors, Applications in graphs  4.3, 4.4 Graph applications: Section 3.3 of Goodaire's text 
Lecture 18  Eigenvalues and Eigenvectors  5.1 
Lecture 19  Similarity and diagonalization  5.2 
Lecture 20  Spectral theorem for real symmetric matrices: case when eigenvalues are distinct 
5.5 
Lecture 21  Complex vector space, Hermitian and unitary matrices  5.5 
Quiz 4  
Lecture 22  Schur's theorem Spectral theorem as a corollary 
5.5 
Lecture 23  Singular value decomposition  6.3 
Midsem Exam 
Part II: Random Processes  
Lecture number  Topics Covered  Section reference (Grimmett's book) 

Lecture 1  Events as sets, probability spaces  1.2 
Lecture 2  Cardinality, countability and infinite sums  Sections 4 and 5 of Manjunath Krishnapur's notes 
Lecture 3  Properties of probability measure  1.3 
Lecture 4  Conditional probability  1.4 
Quiz 5  
Lecture 5  Independence Gambler's ruin 
1.5 
Lecture 6  Random variables and distribution function  2.1 
Lecture 7  Uncountable probability spaces, distribution functions  Section 14 of Manjunath Krishnapur's notes 
Lecture 8  Law of averages  Bernstein's inequality  2.2 
Lecture 9  Discrete r.v.s  definition and examples Independence 
3.1 
Quiz 6  
Lecture 10  Discrete r.v.s  expectation, higher moments and examples  3.3, 3.5 
Lecture 11  Discrete r.v.s  joint distribution function Covariance, correlation 
3.6 
Lecture 12  Discrete r.v.s  conditional distribution and expectation  3.7 
Lecture 13  Discrete r.v.s  conditional expectation Sums of r.v.s 
3.7, 3.8 
Quiz 7  
Lecture 14  Continuous r.v.s  p.d.f., independence, expectation  4.1, 4.2, 4.3 
Lecture 15  Continuous r.v.s  examples  4.4 
Lecture 16  Continuous r.v.s  dependence  4.5 
Quiz 8  
Lecture 17  Continuous r.v.s  conditional distributions and expectation  4.6 
Lecture 18  Continuous r.v.s  functions of r.v.s  4.7 
Lecture 19  Continuous r.v.s  change of variables  4.7 
Lecture 20  Continuous r.v.s  multivariate normal distribution  4.9 