2023 - T3 - WS1 - Fundamental algorithms and algorithmic complexity

Collection 2023 - T3 - WS1 - Fundamental algorithms and algorithmic complexity

Organizer(s) van der Hoeven, Joris ; Giesbrecht, Mark ; Koiran, Pascal ; Villard, Gilles
Date(s) 25/09/2023 - 29/09/2023
linked URL https://indico.math.cnrs.fr/event/8113/
10 17

Computing the non-commutative rank of linear matrices

By Gábor Ivanyos

The topic of the talk connects skew-fields, polynomial identity testing, invariant theory and optimization. By a linear matrix we mean a matrix having homogeneous linear entries and the non-commutative rank is the rank when we consider the variables as elements of the appropriate free skew-field. Computing it is a relaxation of determining the maximal rank of a matrix in a given linear space of matrices. A remarkable characterization can be given in terms of a large common zero block of the coefficient matrices after a change of basis. We will present the main ideas of a deterministic polynomial time algorithm that computes the noncom-mutative rank. Note that existence of an efficient deterministic method computing the ordinary rank is a famous open problem in polynomial identity testing. The algorithm gives lower and upper witnesses for the rank. The lower witness is a polynomial invariant of a sub-matrix while the upper witness is given by a common zero block. We will also discuss some applications of the algorithm. The talk is based on joint works with Youming Qiao and K. V. Subrahmanyam.

Information about the video

Citation data

  • DOI 10.57987/IHP.2023.T3.WS1.010
  • Cite this video Ivanyos, Gábor (27/09/2023). Computing the non-commutative rank of linear matrices. IHP. Audiovisual resource. DOI: 10.57987/IHP.2023.T3.WS1.010
  • URL https://dx.doi.org/10.57987/IHP.2023.T3.WS1.010

Domain(s)

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow




Register

  • Bookmark videos
  • Add videos to see later &
    keep your browsing history
  • Comment with the scientific
    community
  • Get notification updates
    for your favorite subjects
Give feedback