Graphs and Matrices
A PG (MTech/PhD) compulsory course in Systems Science/ICT
Credit: 4 [3 0 0 0]
Objective of the course
Given a data set, graphs can be used to represent the pattern hidden in the data set and matrices are representations of graphs as two dimensional numerical arrays. The course intends to explore the connection between the combinatorial properties of a graph and numerical values associated with its matrix representations and vice versa.
The course contains five modules mentioned below.
Module I: Matrix Algebra (3L) Introduction to matrices, structured matrices (symmetric, Hermitian, positive semi-definite, orthogonal matrix), Matrix algebra structure of set of matrices.
Module II: Introduction to Graphs (3L) Graphs and structured graphs, combinatorial properties of graphs, matrix representation (adjacency matrix and incidence matrix), Laplacian matrix.
Module III: Matrix Analysis (18L) Vector Space, Basis, Orthogonal basis, Similarity of matrices, Rank, Normed Grams-Schmidt process, QR decomposition Schur triangularization theorem, Eigenvalues & Eigenvectors, Location of eigenvalues (Gersgorin disks), Minimal polynomial, Singular value decomposition, Pseudo-inverse, Least-square problem. Jordan canonical form, Positive definite matrices, Polar decomposition
Module IV: Algebraic Graph Theory (11L) Spectrum of graphs, Laplacian matrix associated with a graph, Properties of Laplacian matrix, Line graphs, Tensor product of graphs, Cuts and Flows, Lattice.
Module V: Applications (5L) Graph modelling: Computer Networks, Electrical Networks, Social Networks, Data mining, Search algorithms and many more.
- Understanding matrix as a tool to analyze numerical data.
- Numerical values associated with a matrix provide useful information about the data.
- Connection between graphs and matrices.
- Mathematical structures and properties associated with matrices and graphs.
- R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, 1990.
- R. B. Bapat, Graphs and Matrices, Springer (Hindustan Book Agency), 2011.
- D. B. West, Introduction to Graph Theory, 2nd Edition, Phi Learning, 2009.
- C. Godsil and G. Royle, Algebraic Graph Theory, Springer, 2001.
- C. D. Meyer, Matrix Analysis and Applied Linear Algebra, Cambridge University Press, 2000.
- A. E. Brouwer and W. H. Haemers, Spectra of Graphs, Springer, 2011.
- M. E. J. Newman, Networks: An Introduction, Oxford University Press, 2010.
- Fan Chung, Spectral Graph Theory, American Mathematical Society, 1996.
- L. Elden, Matrix Methods in Data Mining and Pattern Recognition, SIAM, 2007.