Questions tagged [linear-algebra]
Questions about the properties of vector spaces and linear transformations, including linear systems in general.
5,873 questions
12
votes
2
answers
5k
views
Why Householder reflection is better than Givens rotation in dense linear algebra?
It’s obvious that Givens rotation works better with sparse matrices. But I don’t know why Householder reflection is better for dense matrices. Does it require less computations? Or it’s numerically ...
- 253
12
votes
2
answers
1k
views
Quadratic Farkas' Lemma?
The Farkas Lemma says that if a system of linear inequalities implies
yet another linear inequality, then this last inequality can be obtained by
taking a positive linear combination of the ...
- 23k
12
votes
5
answers
9k
views
Solving Lyapunov-like equation
The following matrix equation might be a Lyapunov-like equation, but it seems hard for me to develop a simpler way to solve it. From the computation effort, I need some help for solving the special ...
- 121
12
votes
2
answers
2k
views
Factorization of a matrix as a product of a symmetric and a skew-symmetric matrix
When can an $n\times n$ matrix $M$ be written as a product $M=AB$, where $A^T=A$ and $B^T=-B$?
For example, a necessary condition is that the trace of $M$ vanishes. In this case, it is easy to check ...
- 4,312
12
votes
2
answers
759
views
When Do a Few Eigenvectors of Graph Laplacians Not Determine the Graph?
Essentially as the title, but I'll give a little bit more background.
I have some finite graph $G$ with $n$ vertices and adjacency matrix $A$. Let $D$ be the $n$ by $n$ matrix with the degree of ...
- 193
12
votes
1
answer
3k
views
invariant polynomials on 3 by 3 matrices
Hi there:
A freshman level question here. A polynomial p on the entries of n by n matrices is said to be invariant if p(A)=p(sAs^{-1}) for every invertible matrix s. For example, for 3 by 3 matrices, ...
- 141
12
votes
2
answers
1k
views
Prove/disprove a linear algebra inequality
Setting:
Suppose $\{u_i\}_{i=1}^n \subset R^d$ is a collection of unit vectors such that $u_i^Tu_j < 0$ for all $i\neq j$, and $w$ is a unit vector such that $u_i^T w> 0$ for all $i=1,\dotsc,n$. ...
- 115
12
votes
1
answer
1k
views
Eigenvalues come in pairs
Consider the two matrices with some parameter $s \in \mathbb R$
$$A_1= \begin{pmatrix} s& -1 &0& 0 \\1&0 &0&0 \\ 0&0&1&0 \\0&0&0&1 \end{pmatrix}$$
and
$$...
- 124
12
votes
2
answers
2k
views
Determinant of identity matrix plus Hilbert matrix
I am looking for the determinant
$$ \det(I_n + H_n) $$
where $I_n$ is the $n \times n$ identity matrix and $H_n$ is the $n \times n$ Hilbert matrix, whose entries are given by
$$ [H_n]_{ij} = \frac{...
- 121
12
votes
1
answer
229
views
History of publication of von Neumann's characterization of orthogonally invariant matrix norms
Von Neumann has a result (rather well-known in convex analysis circles) which states that every orthogonally invariant matrix norm (meaning $\| P M Q\| = \| M \|,$ for any orthogonal $P, Q$) is a ...
- 96.4k
12
votes
1
answer
290
views
Largest subset of $GL_n(p)$ in which pairwise subtraction is also in $GL_n(p)$
Suppose $X\subset \mathrm{GL}_n(p)$ is a set of invertible matrices such that for every $A,B\in X$ then also $A-B\in \mathrm{GL}_n(p)\cup \{0\}$. (If anyone knows a name for such sets I would be ...
- 407
12
votes
1
answer
3k
views
Matrix inversion lemma with pseudoinverses
The utility of the Matrix Inversion Lemma has been well-exploited for several questions on MO. Thus, with some positive hope, I'd like to field a question of my own.
Suppose we pick $n$ values $x_1,\...
- 28.6k
12
votes
4
answers
2k
views
Symplectic equivalent of commuting matrices
It is well known what happens if two real symmetric matrices commute, i.e. if we have two matrices $A$ and $B$ such that $A=A^T$, $B=B^T$ and $AB=BA$. The answer is given in terms of diagonalization: ...
- 469
12
votes
1
answer
1k
views
Maximal Number of Pairs of Orthogonal vectors in a set of $n$ vectors in $\mathbb{R}^3$
Suppose you are given a set of $n$ non-zero vectors in $\mathbb{R}^3$. What is the maximum number of pairs of them that are orthogonal? The current guess is $\le 2n$.
EDIT: I forgot to add that no ...
- 928
12
votes
1
answer
2k
views
Comparing Krein-Rutman theorem and Perron–Frobenius theorem
Krein–Rutman theorem is a generalization of Perron–Frobenius theorem, I know that things could be more subtle in infinite dimension, yet there's an important result in Perron–Frobenius that's missing ...
- 273
12
votes
2
answers
8k
views
Is there a way to simplify block Cholesky decomposition if you already have decomposed the submatrices along the leading diagonal?
Let's say we have a block matrix $ M =\left( \begin{array}{ccc}
A & B\\
B^{*} & C \end{array} \right)$ where $M$ is positive definite. ($A$ and $C$ are also positive definite.)
There is a ...
12
votes
2
answers
4k
views
How can one construct a sparse null space basis using recursive LU decomposition?
Given an $m$ by $n$ matrix $A$ I'm familiar with the standard method to compute a basis for the null space of $A$ by computing a QR factorization of $A^T$. If $A$ is large and sparse, we can use ...
- 723
12
votes
1
answer
1k
views
Decomposition of positive definite matrices.
It is known that a $n^2 \times n^2$ positive semidefinite matrix $A$ cannot always be written as a finite sum
$$
A=\sum_{j} B_j \otimes C_j
$$
with $B_j$ and $C_j$ positive semidefinite matrices (of ...
12
votes
3
answers
4k
views
Status of Hadamard matrix conjecture
I would like to know if any progress has been made on Hadamard conjecture :
Hadamard matrix of order $4k$ exists for every positive integer $k$.
- 121
12
votes
2
answers
1k
views
Another $2 \times 2$ matrix question
This question is similar to this previous one but I think it is harder.
Let $X$, $Y$, $Z$, and $W$ be $2\times 2$ Hermitian matrices. Can we always find $\theta,\phi \in [0,\pi/2]$ and $2\times 2$ ...
- 42.8k
12
votes
2
answers
3k
views
How to project a vector onto a very large, non-orthogonal subspace
I have a difficult problem.
I have a very large, non-orthogonal matrix $A$ and need to project the vector $y$ onto the subspace spanning the columns of $A$. If this were a small matrix, I would use ...
- 223
12
votes
3
answers
383
views
Probability of $\ell_1$-norms of vertices of the rotated Hamming cube
Let $O$ be a $d$-dimensional rotation matrix (i.e., it has real entries and $OO^T = O^TO = I$). Let $\mathbf{x}$ be a uniformly random bitstring of length $d$, i.e., $\mathbf{x} \sim U(\{0,1\}^d)$. In ...
- 223
12
votes
2
answers
779
views
Determinant of a checkerboard Hankel matrix with Catalan numbers
My goal is to compute
\begin{equation}
I = \det \left(\mathbf{I} + \mathbf{A}\right)
\end{equation}
where $\mathbf{A}$ is a $n \times n$ checkerboard matrix filled with Catalan numbers:
$$
\left\{
...
- 840
12
votes
3
answers
1k
views
Eigencircles of n x n matrices?
An eigenvalue of a 2 x 2 matrix satisfies the equation
$$ \left(\begin{array}{cc} a & b \\ c & d \end{array} \right)\left( \begin{array}{c} x \\ y \end{array}\right) = \lambda \left( \...
- 22.8k
12
votes
3
answers
607
views
Example of a form linear in infinitely many variables ?
We all know plenty of examples of multilinear forms in finitely many variables (e.g. determinants). However, I am missing an interesting example of a form in infinitely many variables, linear in each. ...
- 4,492
12
votes
1
answer
624
views
Determinants: periodic entries $0,1,2,3$
Consider an $n\times n$ matrix $M_n$ where the sequence
$$\{1,2,3,\dots,n^2\} \mod 4=\{1,2,3,0,1,2,3,\dots\}$$ forms a clock-wise spiral, in that given order. For example,
$$M_4=\begin{bmatrix} 1&...
- 43.2k
12
votes
2
answers
2k
views
(Path) connected set of matrices?
Let $N \in \mathfrak{M}_n(\mathbb{C})$ nilpotent, such that there exists $X \in \mathfrak M_n(\mathbb{C})$ with $X^2=N$ (take for instance $n>2$ and $N(1,n)=1$; $N(i,j)=0$ otherwise).
Denote by $\...
- 2,829
12
votes
2
answers
828
views
Matrices into path algebras
I was thinking about quivers recently, and the following idea came to me.
Let ei,j denote the matrix unit in Mn for 1 ≤ i,j ≤ n. Let Γ denote the complete quiver on vertices {1, …,...
- 1,756
12
votes
2
answers
984
views
Common basis for permutation matrices
How can I check whether there exists a common basis with respect to which two matrices 𝐴 and 𝐵 are permutation matrices?
More explicitly, let $A$ and $B$ be two unitary matrices whose eigenvalues ...
- 295
12
votes
1
answer
295
views
On Sampling rank $r$ matrices
Sample $n^2$ integers $a_{11},\dots,a_{nn}$ in $\{-d,\dots,-1,0,1\dots,d\}$ uniformly.
What is the probability that the resulting matrix $[a_{ij}]$ has rank $r$?
Is there a nice parametrization of ...
- 13.9k
12
votes
1
answer
4k
views
How to check whether a positive integer can be written as linear combination of given others, where all coefficients are positive?
Let $n$, $k$ and $m_1, \dots, m_k$ be positive integers. Which is the most efficient
algorithm to find out whether there are positive integers $a_1, \dots, a_k$ such that
$n = \sum_{i=1}^k a_i m_i$?
...
- 241
12
votes
3
answers
3k
views
How to combine linear constraints on a matrix and its inverse?
Suppose there exists a $(n \times n)$ matrix $A$ that is real and invertible (nothing unusual or special about $A$). We do not know the entries of $A$. However, we do have linear constraints, some of ...
12
votes
1
answer
429
views
The scope of a "strong Cantor-Bernstein" property
This question is of course related to this earlier MO question, but I don't believe is answered by the posts there.
My favorite proof of the Cantor-Schroeder-Bernstein theorem actually establishes ...
- 20.9k
12
votes
0
answers
321
views
Combinatorial proof of invertibility of a symmetric matrix associated to the ring of matrices over a finite field
Let $F$ be a finite field of $q$ elements with characteristic $p$. Let $M_n(F)$ be the ring of $n\times n$ matrices over $F$. We define a $q^{n^2}\times q^{n^2}$ symmetric matrix $L$ over the ...
- 38.6k
12
votes
0
answers
277
views
How many steps on $S_n$ are required to span $V\wedge V$, $V = K^n$?
Let $A$ be a set of generators of $G=S_n$; assume $e\in A$,
$A=A^{-1}$. Let $V = K^n$, $K$ a field. Consider the natural
action of $G$ on $V$ (namely, $g(e_i) = e_{g(i)}$) and on $W = V\wedge V$
(...
- 20.2k
12
votes
0
answers
508
views
More mysterious properties of Gram matrix
This is another question related to the mysterious properties of the Gram matrix in dimension $4$. Here's the previous question.
The following fact could be extracted from 0402087:
For any $a_i\...
- 4,316
12
votes
0
answers
218
views
Which ordering of factors is needed to obtain this kind of determinantal inequalities?
Let $A$ and $B$ be $n\times n$ Hermitian positive definite matrices. The curious determinantal inequality given here, which can be stated as $$\det (A^{4}+ ABBA+BAAB+B^{4})\ge\det(A^{4}+ AABB+BBAA+B^{...
- 13.4k
12
votes
0
answers
314
views
Ratio of entries of A and log A where A is a triangular matrix
Consider triangular matrices $A = \left( {a(n,k)} \right)$ of arbitrary order with $a(n,k) = 0$ if $n + k$ is odd and $a(n,n - 2k) = \frac{{n!}}{{k!(n - 2k)!}}\frac{{(m + n - k - 1)!}}{{(m + n - 1)!}}$...
- 5,622
12
votes
0
answers
825
views
Eigenvalues of permutations of a real matrix: how complex can they be?
This is sort of complementary to this thread. I’ll repeat the definitions here:
For a matrix $M\in GL(n,\mathbb R)$, consider the $n!$ matrices obtained by permutations of the rows (say) of $M$ and ...
- 13.4k
12
votes
0
answers
603
views
On a tentative generalization of the Schmidt decomposition
Background
I am a PhD student in Physics and I am currently developing quite refined computer codes that allow to simulate many-body quantum systems living on a lattice. The difficulty resides in ...
- 141
12
votes
0
answers
349
views
Matroids with prescribed independent sets
Let $A$ be a finite set. Let $B$ be a family of subsets of $A$. We are interested in a matroid with a minimum rank such that every element of $B$ is independent. The answer is obvious - a uniform ...
- 1,791
11
votes
3
answers
1k
views
What is the limit of $a (n + 1) / a (n)$?
Let $a(n) = f(n,n)$ where $f(m,n) = 1$ if $m < 2 $ or $ n < 2$ and $f(m,n) = f(m-1,n-1) + f(m-1,n-2) + 2 f(m-2,n-1)$ otherwise.
What is the limit of $a(n + 1) / a (n)$? $(2.71...)$
11
votes
3
answers
587
views
Is every $A \in \mathrm{SL}_n(\mathbb C)$ a product of four unipotent matrices?
Is every matrix $A \in \mathrm{SL}_n(\mathbb C)$ a product of four unipotent matrices?
I have verified that this is true if $n = 2$, and I believe I have came across this result before. However, I ...
- 485
11
votes
2
answers
10k
views
Derivative of eigenvectors of a matrix with respect to its components
Suppose that $B$ is a real, positive-definitive symmetric ($3\times3$) matrix (more accurately, $B$ is a tensor) with distinct eigenvalues, and that we can write it as
$$
B= \sum_{i=1}^3 \lambda_{i}(...
- 221
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 &...
- 43.2k
11
votes
4
answers
3k
views
Classification of Tori of GL2, up to conjugation
Over an algebraically closed field $k$, every one-dimensional torus embedded (as a closed algebraic subgroup) into GL2 is diagonalisable, and the embedding is $t\mapsto (t^m,t^n)$ for some integers $m,...
- 7,722
11
votes
2
answers
2k
views
Operator that commutes with projections
We investigate the Hilbert space $\ell^2(\mathbb{N}_0)$ with standard orthonormal basis vectors $e_n:=(0,...,0,1,0,...).$
Consider the family of self-adjoint rank $1$ projections $P_n\bullet:= \...
- 536
11
votes
2
answers
777
views
Trace of non-commutable matrices
Let $M_1$ and $M_2$ be two symmetric $d\times d$ matrices. What is the relationship between
$tr(M_1M_2M_1M_2)$ and $tr(M_1^2 M_2^2 )$?
P.S. I tried a few examples and found
$$
tr(M_1M_2M_1M_2) \le tr(...
- 719
11
votes
4
answers
5k
views
Maximum determinant of $\{0,1\}$-valued $n\times n$-matrices
What's the maximum determinant of $\{0,1\}$ matrices in $M(n,\mathbb{R})$?
If there's no exact formula what are the nearest upper and lower bounds do you know?
- 111
11
votes
3
answers
1k
views
Diagonalization via the Toda flow
According to some almost indecipherable notes of a graduate Linear Algebra class, a symmetric matrix $A\in\mathbb R^{n\times n}$ can be diagonalised via the Toda flow. More specifically, if $X=X(t)\in\...
- 2,933