20872 - MATHEMATICAL METHODS IN COMPUTER SCIENCE

The mission of the course is to equip students in the field of computer science with essential mathematical tools derived from linear algebra and discrete mathematics. This course is divided into two main parts: "Topics in Linear Algebra" and "Topics in Discrete Mathematics." In the first part, "Topics in Linear Algebra," students will explore a series of tools, techniques, and principles of linear algebra. They will understand the geometry behind linear algebra, scalar products, norms, and operator norms, applying them to variational problems and optimization. The spectral theorem for Hermitian and Normal operators will be covered, along with Jordan decomposition and the formalism of multilinear algebra. The second part, "Topics in Discrete Mathematics," will cover a series of topics in combinatorics and graph theory. Students will delve into various aspects of combinatorics, mastering techniques such as generating functions, recurrence relations, and asymptotic reasoning. Additionally, students will be introduced to the spectral theory of graphs, exploring the connections between graph theory and linear algebra. Through this course, students will gain the ability to apply mathematical concepts to solve real-world problems in computer science. They will learn to recognize situations where linear algebra and discrete mathematics can provide valuable insights and solutions.

Topics in linear algebra:

1. Review of basic concepts:

• Real and Complex vector spaces, complexification
• Linear operators
• Eigenvalues, eigenfuctions

2. The Geometry of linear algebra:

• Quadratic and Bilinear forms, reduction to canonical form
• Real and Hermitian scalar product
• The group of isometries, orientation*
• Projections, orthogonal projections, variational characterization
• Pseudo Euclidean spaces and Lorentz transformations*
• Affine spaces, affine transformations
• Complements*: Projective spaces, projective transformations, Hyperbolic Geometry

 3. Hermitian and Normal operators

• Hermitian operators
• Normal operators
• Spectral Theorem
• Variational characterization of eigenvalues, Rayleigh quotient, generalized Rayleigh quotient
• Complements*: Infinite dimensional spaces, compact operators, Laplacian and Poincarè inequality

4. Jordan’s Theory

• Principal vectors, cyclic subspaces
• Jordan normal form: Existence and uniqueness
• Applications: Analytic functions of matrices, Caley-Hamilton identity, semigroups of operators

5. Matrix norms

• Norms on vector spaces
• Ring norms of operators, operator norms
• Hilbert-Schmidt scalar product, nuclear norm
• Spectral radius, Gelfand formula, variational characterization of the spectral radius*
• Applications: Singular values, variational characterization, Eckart-Young, the closest rank k-matrix 
• Other applications*: Least square method, pseudoinverse

6. Multilinear Algebra

• Multilinear forms
• Exterior product, exterior algebra
• Determinant, volume
• Cross-product in R^3, applications, and relations with projections
• Complements*: differential forms, non-linear volume transformation, Plucker coordinates

Topics in discrete mathematics:

1. Review of basic concepts

• Set theory
• Functions and relations
• Counting methods
• Countable, uncountable sets

2. Graph theory

• Review of the basics: Terminology, type of graphs, connectivity
• Representation of a graph: Adjacency matrix, Incidence matrix
• Spectral graph theory: The Laplacian matrix and its eigenvalues
• Cheeger inequalities*

3. More on counting:

• Generating functions
• Recurrence relations

4. Asymptotics

• Basics of asymptotic analysis: big O notation, hierarchy
• Big O manipulation, examples
• Asymptotic combinatorics: examples

• Comprehend the geometric concepts involved in the formalism of linear algebra.
• Understand scalar products, norms, and operator norms in real and complex settings.
• Develop familiarity with multilinear operators.
• Understand the application of generating functions and asymptotic arguments in combinatorics.
• Acquire a basic understanding of graph spectral theory.

• Perform diagonalization and reduction to normal Jordan form of matrices, both real and complex, and utilize this process to compute matrix functions.
• Use scalar products, norms, and operator norms in optimization and variational problems.
• Manipulate expressions involving exterior products, inner products, trace operators, and operator functions.
• Solve counting problems using generating functions and recurrence relations.
• Determine the asymptotic growth in recurrence relations and combinatorial problems.

• Face-to-face lectures
• Exercises (exercises, database, software etc.)

Students are assigned weekly exercises that are directly related to the concepts taught during the week. These exercises are meant to be solved independently by the students.

During the subsequent week's class, we will collaboratively solve and engage in discussions on the assigned exercises.

This approach promotes active learning, as students have the opportunity to engage in collaborative problem-solving. By discussing the exercises, students can clarify any misconceptions, deepen their understanding, and learn alternative approaches to problem-solving.

• Partial exams consist of two written exams, one at the midpoint of the course and one at the end. The final grade is calculated as the average of these two scores.
• General exam: written exam at the end of the course that contributes to the overall assessment.

Each written exam comprises five exercises with multiple bullet points covering all the presented material.

A total of 34 points will be assigned, with scores above 34 receiving the maximum grade. The exam evaluates the acquisition of basic knowledge and problem-solving abilities. The exercises vary in difficulty, with the first three emphasizing fundamental concepts and accounting for 25 out of 34 points, while the last two require more problem-solving and critical thinking, accounting for the remaining points.

• Lecture notes of the course
• Introduction to linear algebra. Gilbert Strang
• Linear algebra and learning from data. Gilbert Strang
• Concrete Mathematics. Ronald L. Graham, Donald E. Knuth, Oren Patashnik