Skip to main content

All Questions

Filter by
Sorted by
Tagged with
44 votes
2 answers
2k views

Fermat's Last Theorem for integer matrices

Some years ago I was asked by a friend if Fermat's Last Theorem was true for matrices. It is pretty easy to convince oneself that it is not the case, and in fact the following statement occurs ...
Luis Ferroni's user avatar
  • 1,889
38 votes
10 answers
18k views

Fast matrix multiplication

Suppose we have two $n$ by $n$ matrices over particular ring. We want to multiply them as fast as possible. According to wikipedia there is an algorithm of Coppersmith and Winograd that can do it in $...
ilyaraz's user avatar
  • 1,791
36 votes
2 answers
32k views

Eigenvalues of the product of two symmetric matrices

This is mostly a reference request, as this must be well-known! Let $A$ and $B$ be two real symmetric matrices, one of which is positive definite. Then it is easy to see that the product $AB$ (or $BA$...
kjetil b halvorsen's user avatar
34 votes
1 answer
789 views

Which graphs on $n$ vertices have the largest determinant?

This is a question that seems like it should have been studied before, but for some reason I cannot find much at all about it, and so I am asking for any pointers / references etc. The determinant of ...
Gordon Royle's user avatar
  • 12.7k
29 votes
6 answers
10k views

how to find/define eigenvectors as a continuous function of matrix?

I asked this (with background) here https://stats.stackexchange.com/questions/38494/principal-component-analysis-bootstrap-and-probability-of-eigenvalue-collision but did not really get any answers. ...
kjetil b halvorsen's user avatar
27 votes
1 answer
1k views

Properties to have matrices that commute in $\mathrm{GL}_n(\mathbb C)$

Let $G$ be a finite subgroup of $\mathrm{GL}_n(\mathbb C)$, $A,B \in G$ whose eigenvalues are thus in the unit circle. Assume that the eigenvalues ​​of $A$ are included in a circle arc of length $<\...
user avatar
27 votes
3 answers
13k views

What is known about the distribution of eigenvectors of random matrices?

Let $A$ be a real asymmetric $n \times n$ matrix with i.i.d. random, zero-mean elements. What results, if any, are there for the eigenvectors of $A$? In particular: How are individual eigenvectors ...
Andrew's user avatar
  • 433
26 votes
1 answer
1k views

Real square roots of symmetric matrices

In joint work with Andreas Fischle (TU Dresden, Germany) and Patrizio Neff (U Essen, Germany) we needed to use the following statement: If $S$ is a real $n\times n$ matrix with $S^2$ symmetric, then ...
Lev Borisov's user avatar
  • 5,186
20 votes
2 answers
1k views

Find $Y\in\operatorname{GL}_n(\mathbb{Z})$ such that all eigenvalues of $YX$ are nonnegative

I saw this problem some years ago and I would greatly appreciate any reference or solution. Let $X \in \operatorname{M}_n ( \mathbb{R} )$. Prove that there is $Y \in \operatorname{M}_n ( \mathbb{Z} )$...
jack's user avatar
  • 3,153
18 votes
2 answers
5k views

Nonvanishing of Jacobians implies global injectivity?

I am interested in obtaining injectivity of a $C^1$ map from the nonvanishing minors of its Jacobian matrix. Here is a brief history of the topic. In 1953, Samuelson asked the following: If the ...
Syang Chen's user avatar
18 votes
0 answers
734 views

How boundedly generated is $SL_3(\mathbb{Z})$?

The group $G = \mathrm{SL}_3(\mathbb{Z})$ is known to be boundedly generated, that is, there exists some $m \in \mathbb{N}$, and $g_1, \dots, g_m \in G$ such that we have the following equality of ...
Pablo's user avatar
  • 11.3k
17 votes
2 answers
1k views

The GCD-matrix: generalizing a result of Smith?

Let $M$ be the $n\times n$ matrix, known as the GCD matrix, of entries $M_{ij}=\gcd(i,j)$. In the paper H J S Smith, On the value of a certain arithmetical determinant, Proc. London Math. Soc. 7:208-...
T. Amdeberhan's user avatar
16 votes
4 answers
3k views

How many minors I need to check to conclude all minors will vanish ?

Given a $m \times n$ matrix $n>m$, I was trying to check if all its $m \times m$ minor vanish. I remember hearing that one really does not need to check all possible minors in order to conclude ...
Vagabond's user avatar
  • 1,795
16 votes
3 answers
791 views

Random products of projections: bounds on convergence rate?

The von Neumann-Halperin [vN,H] theorem shows that iterating a fixed product of projection operators converges to the projector onto the intersection subspace of the individual projectors. A good ...
Martin Schwarz's user avatar
15 votes
4 answers
4k views

Kernel of skew-symmetric matrix of rank $n-1$ with $n$ odd: is this a known result?

When $n$ is odd, the kernel of a skew-symmetric matrix $M$ of size $n\times n$ and rank $n-1$ is the span of $v$, where $v$ is a vector whose $i$-th component is the Pfaffian of the matrix obtained by ...
anderstood's user avatar
15 votes
2 answers
477 views

matrix inequality with orthogonal matrices

I would like to know if for $A,B\in SO(3)$ the inequality $$ \|AB-BA\|_F\leq \|A-I\|_F\|B-I\|_F $$ holds, where $\|\cdot\|_F$ denotes the Frobenius norm and $I$ the identity matrix. Using the identity ...
Markus Sprecher's user avatar
14 votes
4 answers
3k views

Vandermonde matrix is totally positive

A totally positive matrix $M\in \mathcal{M}_{n\times m}(\mathbb R)$ is such that all of its minors of all sizes are positive. It is true that any Vandermonde matrix (with well-ordered positive entries)...
Loïc Teyssier's user avatar
14 votes
1 answer
544 views

Are there nice isomorphisms $\operatorname{S}^2(k^n)\cong\Lambda^2(k^{n+1})$?

This might be forced to migrate to math.SE but let me still risk it. The spaces $\operatorname{S}^2(k^n)$ and $\Lambda^2(k^{n+1})$ from the title have equal dimensions. Is there a natural isomorphism ...
მამუკა ჯიბლაძე's user avatar
14 votes
1 answer
1k views

Expansion of $\det(A+B)$

If $A,B\in{\bf M}_n(k)$, then the following formula holds true: $$\det(A+B)=\sum_{r=0}^n\sum_{|I|=|J|=r}\epsilon(I,I^c)\epsilon(J,J^c)A\binom IJ B\binom{I^c}{J^c}.$$ In this formula, $I$ and $J$ are ...
Denis Serre's user avatar
  • 52.3k
13 votes
2 answers
678 views

Closure of the orbits of the $SL(2,\mathbb{Z})$-action on $\mathbb{R}^2$

I'm coming with a very basic question for which I can't find an answer. Please forgive me if I didn't search efficiently enough. What can the closure of an orbit of an element $X$ of $\mathbb{R}^2$ ...
Selim G's user avatar
  • 2,696
13 votes
1 answer
1k views

An inequality for the spectral radius of matrices used by J. Bochi

I am interested in the history of an inequality for the spectral radius of a $d\times d$ real or complex matrix, which occurs in Jairo Bochi's 2002 article Inequalities for numerical invariants of ...
Ian Morris's user avatar
  • 6,206
13 votes
2 answers
414 views

Is every finite-order unimodular matrix conjugate to a $0,1,-1$ matrix?

Problem. Given a matrix $A\in\mathrm{GL}(n,\mathbb{Z})$ such that $A^k=1$ for some $k\geq 1$, is there a matrix $g\in\mathrm{GL}(n,\mathbb{Z})$ such that $gAg^{-1}$ has only $0$, $1$, and $-1$ as ...
Qfwfq's user avatar
  • 23.3k
13 votes
0 answers
237 views

A Dynkin type classification result in linear algebra

Let $G$ be a finite directed acyclic graph. The Cartan matrix $C_G=C$ of $G$ is defined as the matrix with rows and colums indexed by the vertices of $G$ and $c_{i,j}$ counts the number of paths from $...
Mare's user avatar
  • 26.5k
11 votes
3 answers
918 views

yet another determinant and inverse of a matrix

This problem is some variation of another MO question. Consider the matrix $$M_n:=\begin{bmatrix}-c& a & a& \dots & a \\ b & c & a& \ddots & a\\ b & b & -c &...
T. Amdeberhan's user avatar
11 votes
1 answer
1k views

A square root inequality for symmetric matrices?

In this post all my matrices will be $\mathbb R^{N\times N}$ symmetric positive semi-definite (psd), but I am also interested in the Hermitian case. In particular the square root $A^{\frac 12}$ of a ...
leo monsaingeon's user avatar
11 votes
1 answer
632 views

How do computer algebra packages like Sagemath implement rank of a matrix

I am not sure if this is the right place to ask this question, but I believe there will be people here who do computations on computer algebra packages like Sage in their work. I have been using ...
Nikhil's user avatar
  • 263
11 votes
1 answer
948 views

Detailed modern references for basic properties of Pfaffians over commutative rings

Pfaffians are important to algebraic combinatorics, at least. This is to propose the making of a 'wiki' list, more modern, precise and compressed than e.g. the relevant Wikipedia page (nothing against ...
Peter Heinig's user avatar
  • 6,051
11 votes
1 answer
467 views

Correspondence between matrix multiplication and a graph operation of Lovász

In his book "Large networks and graph limits", Lovász describes a multiplication operation (he calls it concatenation) on "bi-labeled graphs". An $(m,n)$ bi-labeled graph is a ...
David Roberson's user avatar
11 votes
1 answer
292 views

Have "sturdy squares" been studied before?

Over on PPCG I've just made a question that involves arranging the numbers 1 to 9 on a 3 by 3 grid such that every 2 by 2 subgrid has the same sum. I'm calling such 3 by 3 grids and their N by N ...
Calvin's Hobbies's user avatar
10 votes
3 answers
829 views

Find the inverse of a matrix that is very similar to the Hilbert matrix

The standard Hilbert matrix $H$ is given by $$H_{ij}=\frac{1}{i+j-1},$$ and it has an inverse given for example in this MO question. Now I have encountered a matrix $M$ of similar form, namely, $$...
Dings's user avatar
  • 153
10 votes
1 answer
537 views

Coefficient-wise powers of matrices. Reference wanted

Let $K$ be a commutative field and ${\rm M}_n (K)$ be the ring of $n\times n$ square matrices with coefficients in $K$ ($n\geqslant 1$ is an integer). For $k\geqslant 1$ and $A =(a_{ij})_{1\leqslant i,...
Paul Broussous's user avatar
10 votes
1 answer
1k views

Maximal order of elements in SL(n,q)

The maximal order of an element of $\mathrm{GL}(n,\mathbb{F}_q)$ is $q^n-1$, where the characteristic of $\mathbb{F}_q$ is odd $p$. See here for a nice proof that uses the Cayley-Hamilton Theorem. ...
Sean Lawton's user avatar
  • 8,529
10 votes
1 answer
520 views

Homogeneous polynomials, mixed determinants, positive definiteness

Are there $n\times n$ real matrices $A_{1}, \ldots, A_{n}$ such that the $n$-homogeneous polynomial $$ f(x_{1}, \ldots, x_{n}) = \det(x_{1} A_{1}+\cdots +x_{n} A_{n}) $$ never vanishes on $\...
Paata Ivanishvili's user avatar
10 votes
0 answers
477 views

Name for an operation on matrices?

Given two matrices $A$ and $B$ of size $a \times n$ and $b \times m$ consider the following operation $A \dagger B$ whose result is an $a b^n \times n m$ matrix. $A \dagger B$ is a block matrix with $...
Grigory Yaroslavtsev's user avatar
9 votes
3 answers
589 views

Subgroup of $\mathrm{GL}_n$ stabilizing linear subspace skew-symmetric matrices

I am currently reading "Schiffer variations and the generic Torelli theorem for hypersurfaces" by Voisin, where it is claimed that the subgroup of $\mathrm{SL}_{2m}$ ($m \geq 3$) which preserves a ...
Libli's user avatar
  • 7,300
9 votes
1 answer
573 views

$SL_2(\mathbf{Z},8\mathbf{Z})$ differs from $E_2(\mathbf{Z},8\mathbf{Z})$. Has this result appeared in the literature?

I know a proof that the congruence subgroup $SL_2(\mathbf{Z},8\mathbf{Z})$ differs from its subgroup $E_2(\mathbf{Z},8\mathbf{Z})$, but can't find this fact in the literature. Does anyone know a ...
Bruce Magurn's user avatar
9 votes
1 answer
472 views

$M = AA^t$ where $A$ has unit norm columns

Let $M \in \mathbb{R}^{k\times k}$ positive definite with $\operatorname{tr} M = m$, where $m$ is an integer such that $m \geq k$. I have found a way (using this answer) to decompose $M = AA^t$ with $...
Yair Daon's user avatar
  • 185
8 votes
4 answers
2k views

Commuting matrices in GL(n,Z)

Suppose $M$ is a "hyperbolic" matrix in $GL(n,\mathbb Z)$, i.e., that its characteristic polynomial $p$ is irreducible over $\mathbb Z$ and has no roots of modulus 1. Is there a closed description ...
Nikita Sidorov's user avatar
8 votes
7 answers
3k views

Source for roots of matrix polynomials?

A matrix polynomial is a polynomial whose variables are square $n \times n$ matrices, let's say with entries in $\mathbb{C}$, and with coefficients in $\mathbb{C}$. I am seeking a source of results on ...
Joseph O'Rourke's user avatar
8 votes
2 answers
2k views

Bounding the minimum singular value of a block triangular matrix

Question: What is the sharpest known lower bound for the minimum singular value of the block triangular matrix $$M:=\begin{bmatrix} A & B \\ 0 & D \end{bmatrix}$$ in terms of the properties ...
Nick Alger's user avatar
  • 1,160
8 votes
3 answers
663 views

Representation theorem for matrices (reference request)

Motivation. If $A \in \mathbb{C}^{n \times n}$ is self-adjoint (or, more generally, normal), then we all know that $$ A = \sum_{k=1}^n \lambda_k \, h_k \otimes h_k, $$ where $\lambda_1,\dots,\lambda_n$...
Jochen Glueck's user avatar
8 votes
3 answers
2k views

Transforming a binary matrix into triangular form using permutation matrices

I am interested in the complexity of the following problem: Given an $m\times n$ binary matrix $M$, can we permute its rows/columns to obtain a triangular matrix? I am also interested in ...
Rob Myers's user avatar
  • 1,271
8 votes
2 answers
377 views

A family of skew-symmetric matrices corresponding to cycles in graphs

When investigating loops in Markov chains I ran into the following observation. A cycle in a graph $G$ with $n$ vertices may be represented by a matrix $\Gamma \in \mathbb R^{n \times n}$ having the ...
Joris Bierkens's user avatar
8 votes
1 answer
441 views

A question on symmetric matrices

$\newcommand{\R}{\mathbb{R}}$ The question is Is there a constructive (say, parametric) description of the set (say $M_n$) of all symmetric matrices $A\in\R^{n\times n}$ such that all the diagonal ...
Iosif Pinelis's user avatar
8 votes
2 answers
948 views

Best known bounds on (border) ranks of small matrix multiplication tensors?

The $(m,n,p)$-matrix multiplication tensor is a representation of the bilinear map $T\colon\mathbb{R}^{m\times n}\times\mathbb{R}^{n\times p}\rightarrow\mathbb{R}^{m\times p}$ given by $T(A,B)=AB$. ...
Dustin G. Mixon's user avatar
8 votes
1 answer
323 views

On a matrix inequality

$\newcommand{\R}{\mathbb R}\newcommand{\tr}{\operatorname{tr}}$It follows from Proposition 7 and this recent answer that, for any positive-definite $n\times n$ symmetric real matrices $A$ and $B$, $$\...
Iosif Pinelis's user avatar
8 votes
1 answer
450 views

Do these matrices have a name?

I am looking for matrices $A\in \mathbb{R}^{m\times n}$ with $m>n$, $A^TA=\frac{m}{n}I$ and $diag(AA^T)=(1\ \dots\ 1)$ where $diag$ denotes the diagonal. Do such matrices have a name? An example ...
user100927's user avatar
8 votes
1 answer
201 views

Growth of powers of non-negative integer matrices

In what I am currently doing, there naturally appears the following question: let $A$ be a square matrix with non-negative integer entries. Let $a_n$ be the sum of all entries of $A^n$. Question: How ...
Victor's user avatar
  • 1,437
8 votes
0 answers
2k views

Possible values of eigenvalues of Hadamard product of Hermitian matrices

One of the most important (and very well-known) result in the study of the spectrum of Hermitian matrices is Horn's conjecture (or theorem?), which provides a complete answer to the following problem: ...
user78370's user avatar
  • 891
7 votes
2 answers
1k views

Dimension of the nilpotent centralizer of a nilpotent matrix

Fix a natural number $n$ and an algebraically closed field $k$. Let $\mathfrak{g}=\mathfrak{gl}_n(k)$. For any partition of $n$, $\lambda=(\lambda_1,\ldots,\lambda_r)$, let $A_{\lambda}$ be the $n\...
Jared's user avatar
  • 768