All Questions
414 questions
3
votes
1
answer
392
views
A particular Lie algebra $L_{n}$ and (various) lie groups whose Lie algebra is isomorphic to $L_{n}$
Edit: According to the comment by @LSpice we realise the existing link to the main motivation of the question is not available. Then we search for the paper we found the following version:
https://www....
- 356
3
votes
2
answers
451
views
Guess the next polynoms in the sequence (MO vs. AI :), count anticommuting $F_p$-matrices, P. Hrubeš conjecture
Here is a sequence of polynoms - (presumably) counting N-tuples of ANTI-commuting 2x2 matrices over $F_p, p>2$. (That is just the case of 2x2 matrices, and (surprisingly) it is not so easy to see a ...
- 24.9k
3
votes
1
answer
381
views
Hadamard $\ell_p$ sum of two symmetric positive semidefinite matrices
Does there exist $p>1$ such that for all $n\geq 2$, if $(a_{ij})$ and $(b_{ij})$ are symmetric positive semidefinite $n\times n$ matrices and $a_{ij}, b_{ij}\geq 0$ then $\bigl(\|(a_{ij},b_{ij})\|...
- 175
3
votes
0
answers
184
views
Matrices with only two different entries and maximal determinant
Define $\mathcal M_n$ as the set of all $n\times n$ matrices of full rank with each entry either 1 or $x$.
I am interested in how big the determinant of such a matrix can be. For this, we define in a ...
- 13.4k
2
votes
0
answers
372
views
What is the Birkhoff norm of a Perron vector?
Let $A$ be a positive matrix. What is known about the Birkhoff norm of its Perron vector?
By the Birkhoff norm of a vector $x$ I refer to the quantity $\frac{\max{x}}{\min{x}}$.
P.S. This is ...
- 6,962
2
votes
0
answers
358
views
Convex combinations $A$ of $n\times n$ permutation matrices such that every entry in $A^{k}$ is $1/n$
Recall that a doubly stochastic matrix is a square matrix $A$ with non-negative entries such that the sum of each row is $1$ and the sum of each column is $1$. The Birkhoff-von Neumann theorem states ...
2
votes
0
answers
105
views
Optimization over a convex cone generated by a set is equal to optimization over the set
Within my research I found an important doubt and that prevents me from advancing, the context of my doubt is as follows:
We considerer the following optimization problem
$$
\left\{\begin{array}{cl} \...
- 159
2
votes
0
answers
92
views
Hadamard $\ell_p$ sum of two symmetric positive semidefinite matrices: follow-up
I asked the following question here: "Does there exist $p>1$ such that for all $n\geq 2$, if $(a_{ij})$ and $(b_{ij})$ are symmetric positive semidefinite $n\times n$ matrices and $a_{ij}, b_{ij}\...
- 175
1
vote
1
answer
276
views
Spectral decomposition of a $4\times4$ real nonsymmetric matrix with unknown elements
I'm trying to eigendecompose the following matrix $A$, i.e. to find $Q$ and $\Lambda$ such that
$$
A = \begin{bmatrix}
-\alpha & \alpha & -\gamma^{-1} & 0\\
\beta &...
- 207
1
vote
0
answers
455
views
Possibility of Disconnected Subgraphs of a $k$ Connected $r$ regular Graph under a given condition
Context: Given a adjacency matrix A of a $r$-regular graph $G$ (not complete graph $K_{r+1}$) . $G$ is $k$ connected.
The matrix A can be divided into 4 sub-matrices based on adjacency of vertex $x ...
- 267
1
vote
1
answer
381
views
A geometric property of singular matrices
Let $S\subset M_{n}(\mathbb{R})$ be the singular points of the equation $Det=0$. That is $S$ is the critical points of the determinant function.
What matrices belongs to $S$, precisely?
Let $M=...
- 356
1
vote
1
answer
1k
views
Expected size of determinant of $AA^T$ for non-square random $A$
If $A$ is chosen uniformly at random over all possible $m \times n$ (0,1)-matrices, what is the expected size of the absolute value of the determinant of $AA^T$. We can assume $m < n$ and all ...
- 3,377
1
vote
0
answers
167
views
Why is Givens better than Householder on sparse matrix? [closed]
I am trying to transform a matrix from something like
a b c
d e f
g h i
to
0 b 0
d 0 f
0 h 0
but at a way larger scale. ...
1
vote
1
answer
462
views
Is this a full rank matrix? [closed]
According to the answer of znt to the previous version, I revise the question as follows:
Is there a real $(n-1)\times n$ matrix $A$
such that $A$ is not a full rank matrix and satisfy $a_{ii}&...
- 356
1
vote
1
answer
266
views
Combinatorial 0-1 vector problem
Let $M \in \{0, 1\}^{n\times n}$.
Given a constant integer $c \ge 2$, let the number of $1$s in each row be equal to $\frac{n}{c}$ (assuming $c$ is a divisor of $n$). Let $\mathcal{M}_c$ be the set of ...
- 1,677
1
vote
0
answers
122
views
Hard instances for this graph isomorphism algorithm based on powers of weighted adjacency matrices?
In short, I found an algorithm for GI and the only hard instances
I found so far are non-isomorphic strongly regular graphs with
large automorphism groups.
Q1 What are hard instances for the ...
- 25.4k
0
votes
0
answers
61
views
Combinatorial counting question related to count (anti)commuting N-tuples of matrices (more generally $(X_1,...X_n): F(X_i,X_j)=0$ - only one F)
Consider some finite set $S$ (can be matrices over $F_p$), consider some symmetric relation $F(s1,s2)$ which values are True or False (for example - matrices (anti)commutate or not).
Question 1: can ...
- 24.9k
0
votes
1
answer
744
views
A RKHS interpretation of the Rydberg formula for hydrogen and an application for physics?
I was thinking if it is possible to define an inner product between two small physical objects with a positive definite kernel and was led to look at the Rydberg formula:
The Rydberg formula for ...
- 3,054
66
votes
2
answers
8k
views
Geometric interpretation of characteristic polynomial
The coefficients of lowest and next-highest degree of a linear operator's characteristic polynomial are its determinant and trace. These have well-known geometric interpretations. But what about its ...
- 2,071
63
votes
7
answers
9k
views
How to prove this determinant is positive?
Given matrices
$$A_i= \biggl(\begin{matrix}
0 & B_i \\
B_i^T & 0
\end{matrix} \biggr)$$
where $B_i$ are real matrices and $i=1,2,\ldots,N$, how to prove the following?
$$\det \big( I + e^...
- 845
42
votes
4
answers
33k
views
What is the intuition for the trace norm (nuclear norm)?
I will word this question in terms of linear operators acting on $\mathbb{C}^n$ for simplicity. Feel free to provide an answer in terms of more general Hilbert spaces if you think it makes more sense ...
- 539
40
votes
6
answers
6k
views
Linear transformation that preserves the determinant
It seems "common knowledge" that the following holds:
Let $T$ be a linear transformation on $n\times n$ matrices with complex coefficients that preserves the determinant. Then there exists ...
- 511
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 $...
- 1,791
36
votes
4
answers
2k
views
Determinant of the random matrix $X^2+Y^2$
$\DeclareMathOperator\Prob{Prob}$Let $X,Y\in M_n(\mathbb{R})$ be $2$ random matrices. The entries of $X,Y$ are i.i.d. variables. They follow the standard normal law $N(0,1)$.
i) When $n=2,3,4$, one ...
- 3,741
35
votes
3
answers
4k
views
A curious determinantal inequality
In my study, I come across the following curious inequality, which I do not know a proof yet (so I am asking it here).
Let $A, B$ be $n\times n$ (Hermitian) positive definite matrices. It is very ...
- 1,748
34
votes
3
answers
3k
views
Quickly determining if a matrix has any PSD completion
Given $m$ entries of an $n \times n$ matrix, is it possible to determine in $O(m n)$ time whether there is any positive semidefinite completion?
Slightly more precisely: for simplicity let's assume ...
- 777
34
votes
3
answers
6k
views
Why is uncomputability of the spectral decomposition not a problem?
Below, we compute with exact real numbers using a realistic / conservative model of computability like Type Two Effectivity.
Assume that there is an algorithm that, given a symmetric real matrix $M$, ...
- 4,943
32
votes
0
answers
649
views
Existence of orthogonal basis of symmetric $n\times n$ matrices, where each matrix is unitary?
For a positive integer $n$, let $S_n$ denote the set of $n\times n$ symmetric matrices over $\mathbb{C}$. As a complex vector space, this set has dimension $\mathrm{dim}(S_n)=\binom{n+1}{2}$. The ...
- 481
31
votes
1
answer
4k
views
Determinants of binary matrices
I was surprised to find that most $3\times 3$ matrices with entries in $\{0,1\}$ have determinant $0$ or $\pm 1$. There are only six out of 512 matrices with a different determinant (three with $2$ ...
- 12.7k
29
votes
12
answers
6k
views
When does 'positive' imply 'sum of squares'?
Does anyone have examples of when an object is positive, then it has (or does not have) a square root? Or more generally, can be written as a sum of squares?
Example. A positive integer does not ...
29
votes
1
answer
3k
views
Is there an explicit formula for the hessian of "Determinant"?
Let $f: G= \mbox{GL}(n,\mathbb{R}) \to \mathbb{R}$ be the determinant function.
Then $\mbox{Hess} (f)$ is a two linear map on $M_{n}(\mathbb{R})\simeq T_{e}(G)$ where $e$ is the neutral element of $G$,...
- 356
29
votes
6
answers
8k
views
How to find a closest integer point to the intersection of two lines?
Here's a question that originates from StackOverflow.
Given are two lines on a plane, specified by equations ($a x + b y = c$) with integer coefficients. The lines aren't parallel and they don't ...
- 391
27
votes
2
answers
1k
views
Uniquely reconstruct a matrix $M$ from its inverse $M^{-1}$ if $n$ elements of $M^{-1}$ are unknown and $n$ elements of $M$ are given
This question was motivated by a recent MO post. You know $n$ elements of the $N\times N$ matrix $M$ and you do not know $n$ elements of the inverse $M^{-1}$ (but you know the other $N^2-n$ elements ...
- 188k
26
votes
5
answers
1k
views
Condition for a matrix to be a perfect power of an integer matrix
I have a question that seems to be rather simple but for I got no clue so far.
Let's say I have a matrix $A$ of size $2\times 2$ and integer entries. I want to know if there is a kind of test or ...
- 1,889
26
votes
2
answers
4k
views
Finite subgroups of unitary groups
Let $n$ be an integer. Camille Jordan showed that there exists some $m \in {\mathbb N}$ (depending on $n$), such that for any pair of $n \times n$-unitaries $u,v \in U(n)$ which generate a finite ...
- 25.5k
26
votes
6
answers
14k
views
Deriving inverse of Hilbert matrix
The Hilbert matrix is the square matrix given by
$$H_{ij}=\frac{1}{i+j-1}$$
Wikipedia states that its inverse is given by
$$(H^{-1})_{ij} = (-1)^{i+j}(i+j-1) {{n+i-1}\choose{n-j}}{{n+j-1}\choose{n-...
- 1,254
22
votes
4
answers
5k
views
Eigenvalues of permutations of a real matrix: can they all be real?
For a matrix $M\in GL(n,\mathbb R)$, consider the $n!$ matrices obtained by permutations of the rows (say) of $M$ and define the total spectrum $TS(M)$ as the union of all their spectra (counting ...
- 13.4k
22
votes
1
answer
13k
views
Non-diagonalizable complex symmetric matrix
This is a question in elementary linear algebra, though I hope it's not so trivial to be closed.
Real symmetric matrices, complex hermitian matrices, unitary matrices, and complex matrices with ...
- 23.3k
21
votes
4
answers
9k
views
Condition for two matrices to share at least one eigenvector?
Suppose that I have two matrices $A$ and $B$, and I want them to share a common eigenvector $x$. For simplicity let's just assume that the eigenvalue associated with $x$ is $1$ for both matrices, so $...
- 403
20
votes
4
answers
2k
views
Does Anyone Know Anything about the Determinant and/or Inverse of this Matrix?
The matrix I am inquiring about here is the $n \times n$ matrix where the entry $A_{ij}$ is $\frac{1}{(i+j-1)^2}$. The $2 \times 2$ matrix looks like
$$
\begin{pmatrix}
1 & 1/4 \\
1/4 & 1/9
\...
- 209
19
votes
1
answer
2k
views
Smallest eigenvalue of a tricky random matrix
While experimenting with positive-definite functions, I was led to the following:
Let $n$ be a positive integer, and let $x_1,\ldots,x_n$ be sampled from a zero-mean, unit variance gaussian. Consider ...
- 28.6k
19
votes
1
answer
856
views
A possible extension of a determinant inequality
It is well known that if $A, B$ are positive semidefinite matrices, then $$\det (A+B)\ge \det A+\det B.$$
I am considering a possible extension of this result. Let $\mathbb{M}_m(\mathbb{M}_n)$ ...
- 1,748
19
votes
3
answers
2k
views
Best known bounds on tensor rank of matrix multiplication of 3×3 matrices
Years ago I attended a conference where they taught us that matrix multiplication can be represented by a tensor. The rank of the tensor is important, because putting it into minimal rank form ...
- 3,359
19
votes
3
answers
2k
views
Is the semigroup of nonnegative integer matrices with determinant 1 finitely generated?
The group of $n\times n$ matrices with integer entries and determinant equal to 1, $SL(n,Z)$, is a finitely generated group (in fact, it is generated by 2 matrices). I am interested to know if the ...
- 1,045
19
votes
4
answers
1k
views
Applications of linear programming duality in combinatorics
So, I know that one can apply the strong LP duality theorem to specific instances of maximum flow problems to recover some nontrivial theorems in combinatorics, such as Hall's theorem, Koenig's ...
- 997
18
votes
3
answers
1k
views
looking for proof or partial proof of determinant conjecture
Math people:
I am looking for a proof of a conjecture I made. I need to give two definitions. For distinct real numbers $x_1, x_2, \ldots, x_k$, define $\sigma(x_1, x_2, \ldots, x_k) =1$ if $(x_1, ...
- 533
18
votes
3
answers
1k
views
Orthogonal matrices with small entries
Is it true that for any $n$, there exists a $n \times n$ real orthogonal matrix with all coefficients bounded (in absolute value) by $C/\sqrt{n}$, $C$ being an absolute constant ?
Some remarks :
If ...
- 4,653
18
votes
3
answers
3k
views
Deciding membership in a convex hull
Given points $u, v_1, \dots,v_n \in \mathbb{R}^m$, decide if $u$ is contained in the convex hull of $v_1, \dots, v_n$.
This can be done efficiently by linear programming (time polynomial in $n,m$) in ...
- 667
18
votes
3
answers
950
views
Bounding the commutator [A,B] in terms of the numerical radius
Given a norm $N$ over ${\bf M}_n(\mathbb C)$, it is a natural question to find the best constant $C_N$ such that
$$N([A,B])\le C_N N(A)N(B),\qquad\forall A,B\in{\bf M}_n(\mathbb C).$$
The answer is ...
- 52.3k
17
votes
1
answer
7k
views
How can we interpret the eigenvalues and eigenvectors of Euclidean Distance Matrices?
I asked this question in Math Stack Exchange earlier here: https://math.stackexchange.com/questions/1199380/what-is-the-intuition-behind-how-can-we-interpret-the-eigenvalues-and-eigenvec and since I ...
- 271