University of Birmingham > Talks@bham > Optimisation and Numerical Analysis Seminars > Tropical matrix roots

Tropical matrix roots

Add to your list(s) Download to your calendar using vCal

  • UserDaniel Jones (INRIA and Ecole Polytechnique, Paris)
  • ClockThursday 02 November 2017, 12:00-13:00
  • HouseSandbox (Watson).

If you have a question about this talk, please contact Sergey Sergeev.

We explore the problem of finding positive integer roots of finite square matrices in the tropical algebra – where ordinary addition is replaced by maximisation, ordinary multiplication is replaced by addition and all operations are extended to vectors and matrices in the usual way. Note that it was shown by M. Kutz that finding kth roots of Boolean matrices (equivalently kth roots of digraphs), for any fixed positive integer k > 1, is NP-complete. We define (with justification) positive integer roots of finite matrices in the 2 by 2 case. For a special case, we generalise results to finite n by n matrices.

Finally, we note some interesting links between the matrix root problem and the set of idempotent matrices in tropical algebra (matrices A such that A = A^2) and we pose some open questions relating to the existence of matrix roots and approximations of matrix roots.

This talk is part of the Optimisation and Numerical Analysis Seminars series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on talks.cam from the University of Cambridge.