All Questions
6,026 questions
22
votes
3
answers
3k
views
Splitting the determinant polynomial into linear factors - a Dedekind problem
Here's the question in a nutshell. For some $n\in\mathbb N$, we consider the polynomial
$\det\left(\left(X_{i,j}\right) _ {1\leq i\leq n,\ 1\leq j\leq n}\right)\in\mathbb Z\left[X_{i,j}\mid 1\leq i\...
- 33.8k
22
votes
2
answers
4k
views
Fast Fourier transform for graph Laplacian?
In the case of a regularly-sampled scalar-valued signal $f$ on the real line, we can construct a discrete linear operator $A$ such that $A(f)$ approximates $\partial^2 f / \partial x^2$. One way to ...
- 3,059
21
votes
7
answers
2k
views
Modern developments in finite-dimensional linear algebra
Are there any major fundamental results in finite-dimensional linear algebra discovered after early XX century? Fundamental in the sense of non-numerical (numerical results, of course, are still ...
- 263
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
2
answers
2k
views
Real rootedness of a polynomial
Let's consider $m$ and $n$ arbitrary positive integers, with $m\leq n$, and the polynomial given by:
$$ P_{m,n}(t) := \sum_{j=0}^m \binom{m}{j}\binom{n}{j} t^j$$
I've found with Sage that for every $...
- 1,889
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
3
answers
1k
views
What is the set of all "pseudo-rational" numbers (see details)?
Define a “pseudo-rational” number to be a real number $q$ that can be written as
$q=\sum_{n=1}^{\infty} \frac{P(n)}{Q(n)}$
Where $P(x)$ and $Q(x)$ are fixed integer polynomials (independent of n). ...
- 311
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
1
answer
3k
views
Density of polynomials in $C^k(\overline\Omega)$
Let $\Omega$ be an open and bounded subset of $\mathbb{R}^2$ and let $C^k(\Omega)$, $1\leq k<\infty$, be the space of functions $f$ with continuous derivatives of order $\leq k$ in $\Omega$, ...
- 4,034
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
557
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.9k
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
2
answers
2k
views
Constants for Rolle's Theorem applied to polynomials
Rolle's Theorem states that $f(1/2)=f(-1/2)+f'(x)$ has a root in the open real
interval $(-1/2,1/2)$ if $f$ is continuous and differentiable. How large can the absolute value of such a root
$\xi$
be ...
- 17.9k
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.9k
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