All Questions
6,253 questions
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
21
votes
9
answers
19k
views
What is the best algorithm to find the smallest nonzero Eigenvalue of a symmetric matrix?
see title.
An algorithm is 'good' if it is able to distinguish between zero Eigenvalues and nonzero Eigenvalues.
- 979
21
votes
6
answers
2k
views
What are the possible eigenvalues of these matrices?
Edit: since we seem a bit deadlocked at this point, let me weaken the question. It's fairly easy to see that the set of 8-tuples of reals which can be the eigenvalues of a matrix of the desired form ...
- 42.8k
21
votes
5
answers
2k
views
The middle eigenvalues of an undirected graph
Let $ \lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_{2n} $
be the collection of eigenvalues of an adjacency matrix of an undirected graph $G$ on $2n$ vertices. I am looking for any work or references ...
- 784
21
votes
4
answers
4k
views
Rings over which every module is free
We know that modules over skewfields are free. Is the converse true? In other words, is it true that a nontrivial ring over which every module is free is a skewfield?
If the ring A is commutative, ...
- 1,069
21
votes
3
answers
51k
views
What is the time complexity of truncated SVD?
Full SVD, on an $m \times n$ matrix $A$, [U,S,V] = svd(A), would cost $O(m^2n + mn^2 + n^3)$ time. But what is the time complexity if we only need the $k$ largest ...
- 327
21
votes
4
answers
3k
views
Computing the Zariski closure of a subgroup of SL(n,Z)
Suppose $\Gamma$ is a finitely generated subgroup of $SL(n,\mathbb{Z})$, given as a list of generators. We would like to (somewhat efficiently) try to compute the Zariski closure of $\Gamma$, which is ...
- 3,201
21
votes
2
answers
18k
views
Complexity of linear solvers vs matrix inversion
Solving linear equations can be reduced to a matrix-inversion problem, implying that the time complexity of the former problem is not greater than the time complexity of the latter. Conversely, given ...
- 1,207
21
votes
2
answers
1k
views
Closed subspaces of Banach spaces
Is it true that, assuming the Axiom of Choice, every infinite-dimensional Banach space has an infinite-dimensional closed subspace with infinite codimension? Note that this is different from the ...
- 2,049
21
votes
1
answer
2k
views
Almost commuting unitary matrices
Suppose that $A_1,\dots, A_k$ are unitary matrices such that any two of them can be approximated by commuting unitary matrices. i.e. for any $i$ and $j$, there are unitary matrices $A_i'$ and $A_j'$ ...
- 901
21
votes
1
answer
653
views
Characteristic polynomial of the Gcd matrix
Let $A_n$ be the $n \times n$-matrix with entries $\gcd(i,j)$ and $f_n$ the characteristic polynomial of $A_n$.
Question: Is $f_n$ irreducible over $\mathbb{Q}$ for all $n$ except $n=8$?
This is ...
- 26.5k
21
votes
3
answers
1k
views
Which doubly stochastic matrices can be written as products of pairwise averaging matrices?
A matrix $A$ is called doubly stochastic if its entries are nonnegative, and if all of its rows and columns add up to $1$. A subset of doubly stochastic matrices is the set of pairwise averaging ...
- 415
21
votes
0
answers
520
views
Is the exponent of $2$ in the Pythagorean theorem the "same $2$" as $[\mathbb{C} : \mathbb{R}]$?
I posted this question in Math StackExchange a couple years ago; due to the recent surge in interest, and following the feedback of several users, I've decided to cross-post it here. I apologize for ...
- 1,206
21
votes
0
answers
904
views
Cauchy matrices with elementary symmetric polynomials
$\newcommand{\vx}{\mathbf{x}}$
Let $e_k(\vx)$ denote the elementary symmetric polynomial, defined for $k=0,1,\ldots,n$ over a vector $\vx=(x_1,\ldots,x_n)$ by
\begin{equation*}
e_k(\vx) := \sum_{1 \...
- 28.6k
20
votes
8
answers
3k
views
Finitely presented sub-groups of $\operatorname{GL}(n,C)$
Here are two questions about finitely generated and finitely presented groups (FP):
Is there an example of an FP group that does not admit a homomorphism to $\operatorname{GL}(n,C)$ with trivial ...
- 28.9k
20
votes
7
answers
5k
views
Why do infinite-dimensional vector spaces usually have additional structure?
On Mathematics Stack Exchange, I asked the following question: Why are infinite-dimensional vector spaces usually equipped with additional structure? Although it received one good answer, I feel that ...
- 961
20
votes
6
answers
42k
views
Eigenvalues of symmetric tridiagonal matrices
Suppose I have the symmetric tridiagonal matrix:
$$ \begin{pmatrix}
a & b_{1} & 0 & ... & 0 \\\
b_{1} & a & b_{2} & \ddots & \vdots \\\
0 & b_{2} & a & \...
20
votes
3
answers
3k
views
Small-index subgroups of SL(3,Z)
I would like to know the smallest-index subgroups of ${\rm SL}(3,\mathbb{Z})$.
The smallest I could find has even entries $a_{3,1}$ and $a_{3,2}$,
along the bottom row. I could not figure out ...
- 743
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
20
votes
4
answers
2k
views
The sum of same powers of all matrices modulo p
The following is a problem from our department algebra competition for
students:
Non-question.
An experimental-math geek was trying to raise all matrices $17\times17$
over the field with 17 ...
- 3,932
20
votes
3
answers
6k
views
When is $\ker AB = \ker A + \ker B$?
Prove/ Disprove: Let $n$ be a positive integer. Let $A$, $B$ be two $n \times n$ square matrices over the complex numbers. If $AB = BA$ and $\ker A = \ker A^2$ and $\ker B = \ker B^2$
then $\ker AB = ...
- 685
20
votes
4
answers
2k
views
Nuances Regarding Naturality
It's frequently said, informally, that a natural isomorphism is one that doesn't depend on arbitrary choices.
But the phrase "arbitrary choices" lends itself to different interpretations. Consider ...
- 23k
20
votes
2
answers
5k
views
How are eigenvalues and eigenvectors affected by adding the all-ones matrix?
Given an $n \times n$ matrix $A$ and the $n\times n$ all-ones matrix $J = (1)_{ij}$, I'm interested in the relation between the eigenvalues and eigenvectors of the matrices $A$ and $A+J$, or more ...
- 1,142
20
votes
3
answers
2k
views
Approximating commuting matrices by commuting diagonalizable matrices
Suppose the matrices $A$ and $B$ commute. Do there exists sequences $A_n$ and $B_n$ of matrices such that
$A_n \rightarrow A$, $B_n \rightarrow B$.
Each $A_n$ is diagonalizable and the same for ...
- 571
20
votes
1
answer
754
views
Minimum value of $|p(1)|^2+|p(2)|^2 +...+ |p(n+3)|^2$ over all monic polynomials $p$
Let $n$ be a positive integer. Determine the smallest possible value of $|p(1)|^2+|p(2)|^2 +...+ |p(n+3)|^2$ over all monic polynomials $p$ of degree $n$.
This question was proposed (problem A.611)
...
- 3,153
20
votes
4
answers
5k
views
Is the pseudoinverse the same as least squares with regularization?
Given a linear system $Ax=b$, the pseudoinverse of $A$ is found as the matrix $A^+$ such that $x=A^+ b$ where $x$ solves the least squares problem $\min \| Ax - b \|^2 $ and $x \perp \mathcal{N}(A)$. ...
- 501
20
votes
1
answer
556
views
Almost orthogonal maps $f:\omega \to \{-1,1\}$
Let $\omega$ denote the set of non-negative integers. For sets $A,B$, let $B^A$ denote the set of maps $f:A\to B$. For $f,g\in\{-1,1\}^\omega$ we say that $f,g$ are almost orthogonal if there is $C_0\...
- 48.8k
20
votes
2
answers
1k
views
a determinantal identity
Dusan Pokorny and Jan Rataj have just posted a paper (http://arxiv.org/abs/1209.2305) in which they prove the identity
$$
\det (A-B) = \frac 1{d!} \sum_{k=0}^d (-1)^k \binom dk \det((d-k)A + kB)
$$
...
- 340
20
votes
3
answers
813
views
Basis removal gives a basis
Let $V$ be a vector space. Let us say that a finite set $X$ of vectors in $V$ is harmonic if for $B \subseteq X$,
$$
B \text{ is a basis of } V \implies X \setminus B \text{ is a basis of }V.
$$
Let ...
- 3,932
20
votes
2
answers
1k
views
Euler numbers and permanent of matrices
Motivated by Question 402249 of Zhi-Wei Sun, I consider the permanent of matrices
$$e(n)=\mathrm{per}\left[\operatorname{sgn} \left(\tan\pi\frac{j+k}n \right)\right]_{1\le j,k\le n-1},$$
where $n$ is ...
- 884
20
votes
3
answers
1k
views
Simultaneous "orthonormalization" in $\mathbb{C}^4$
Let $A$ be a positive, invertible $4 \times 4$ hermitian complex matrix.
So we have a positive sesquilinear form $\langle Av,w\rangle$. Say that a pair $(v,w)$ of vectors in $\mathbb{C}^4$ is good ...
- 42.8k
20
votes
2
answers
1k
views
Spectral radius on 0-1 vectors.
Let $A$ be an $n\times n$ symmetric substochastic matrix (i.e. all entries are non-negative and each row adds up to $1$ or less).
Call a vector $v \in \mathbb{R}^n$ an indicator if $v \neq 0$ and ...
- 4,304
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} )$...
- 3,153
19
votes
17
answers
7k
views
Vector spaces without natural bases
Does anyone know any nice examples of vector spaces without a basis that is in some sense "natural".
To clarify what I mean, suppose we look at $\mathbb{R}^2$. We define $\mathbb{R}^2$ as pairs of ...
19
votes
2
answers
2k
views
How to prove positivity of determinant for these matrices?
Let $g(x) = e^x + e^{-x}$. For $x_1 < x_2 < \dots < x_n$ and $b_1 < b_2 < \dots < b_n$, I'd like to show that the determinant of the following matrix is positive, regardless of $n$:
...
- 325
19
votes
3
answers
6k
views
What are the matrices preserving the $\ell^1$-norm?
So I am inspired by unitary matrices which preserve the $\ell^2$-norm of all vectors, so in particular the unit norm vectors. But then I saw that the $\ell^1$-norm of probability vectors is preserved ...
- 391
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
19
votes
1
answer
3k
views
Non-degenerate alternating bilinear form on a finite abelian group
I asked this question on math.stackexchange yesterday, but nobody has helped so far, and only 44 people have seen it! So I hope people do not mind me asking it here...
Let $A$ be a finite abelian ...
- 831
19
votes
2
answers
9k
views
Distributing the Hodge map over the wedge product
Let $(V,\langle,\rangle)$ be a finite dimensional inner product space, $V^{\wedge}$ it exterior algebra, and $\ast$ the Hodge star arising from $\langle,\rangle$. Does there exist any formula to "...
- 191
19
votes
4
answers
7k
views
Sherman-Morrison type formula for Moore-Penrose pseudoinverse
Given an $n\times n$ invertible matrix $\mathbf A$ and two column vectors $\mathbf u$, $\mathbf v\in\mathbb R^n$, suppose that $1 + {\mathbf v}^T {\mathbf A}^{-1}\mathbf u \neq 0$.
Then the Sherman-...
19
votes
5
answers
1k
views
List of counting proofs instead of linear algebra method in combinatorics
I've just come across this proof of the Graham-Pollak Theorem by Sundar Vishwanathan (thanks to Konrad Swanepoel's sporadic comments about it on this site), that must be called beautiful after its ...
- 18.7k
19
votes
4
answers
2k
views
Problems concerning subspaces of $M_n(\mathbb{C})$
Let $M_n(\mathbb{C})$ denote the n times n matrices over the complex number field. N be a subspace of $M_n(\mathbb{C})$.
If all the matrices in N are non-invertible , what is the maximum the ...
- 363
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
4
answers
719
views
The rank of a perturbed triangular matrix
$\DeclareMathOperator{\rk}{rk}$
The question below is implicit in this MO post, but I believe it deserves to be asked explicitly, particularly now that I have some more numerical evidence.
Suppose ...
- 23k
19
votes
2
answers
1k
views
Exponentiation of vector spaces?
This question occurred to me while thinking on another one here, Name for an operation on matrices?
Can one define in an invariant way a binary operation on finite-dimensional vector spaces - let us ...
- 18.4k
19
votes
1
answer
494
views
Linear maps between arbitrarily chosen vectors of vector spaces $V$ and $W$
I recently came across this question:
Is the axiom of choice needed to prove the following statement:
Let $V, W$ be vector spaces, and suppose $V \neq \{0\}$. Let $v \in V$, $v \neq 0$, $w \in W$. ...
- 191
19
votes
1
answer
690
views
What is the groupoid cardinality of the category of vector spaces over a finite field?
For any groupoid, it's groupoid cardinality is the sum of the reciprocals of the automorphism groups over the isomorphism classes. Let us consider the category of vector spaces over a finite field $\...
- 7,746
19
votes
3
answers
2k
views
Research level applications of "row rank = column rank"?
No less an authority than Gilbert Strang frames "row rank equals column rank" (and a couple of other facts) as "The Fundamental Theorem of Linear Algebra."
I'd simply like to assemble (for teaching ...
19
votes
2
answers
2k
views
Is the tensor product of polyhedra a polyhedron?
Conventions: A polytope in a finite-dimensional $\mathbb R$-vector space $V$ is defined to be a convex hull of finitely many points in $V$. A polyhedron in a finite-dimensional $\mathbb R$-vector ...
- 33.8k
19
votes
4
answers
2k
views
Variation on a matrix game
The original problem appeared on last year's Putnam exam:
"Alan and Barbara play a game in which they take turns filling entries of an initially empty 2008×2008 array. Alan plays first. At each turn, ...
- 1,975