Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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, ...
Benoit Jubin's user avatar
  • 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 ...
user40484's user avatar
  • 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 ...
Alex Eskin's user avatar
  • 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 ...
Alm's user avatar
  • 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 ...
Bruce Blackadar's user avatar
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'$ ...
Omid Hatami's user avatar
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 ...
Mare's user avatar
  • 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 ...
angela's user avatar
  • 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 ...
pregunton's user avatar
  • 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 \...
Suvrit's user avatar
  • 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 ...
Dmitri Panov's user avatar
  • 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 ...
Joe Lamond's user avatar
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 & \...
FlamingWilderbeest's user avatar
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 ...
David Farmer's user avatar
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 \...
user36887's user avatar
  • 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 ...
Anton Klyachko's user avatar
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 = ...
Manoj's user avatar
  • 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 ...
Steven Landsburg's user avatar
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 ...
Somatic Custard's user avatar
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 ...
user21162's user avatar
  • 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) ...
jack's user avatar
  • 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)$. ...
Herman Jaramillo's user avatar
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\...
Dominic van der Zypen's user avatar
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) $$ ...
Joe Fu's user avatar
  • 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 ...
Anton Klyachko's user avatar
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 ...
Deyi Chen's user avatar
  • 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 ...
Nik Weaver's user avatar
  • 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 ...
Pablo Lessa's user avatar
  • 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} )$...
jack's user avatar
  • 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$: ...
Charlie Yun's user avatar
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 ...
D. Rusin's user avatar
  • 391
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 ...
Giuseppe's user avatar
  • 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 "...
user49105's user avatar
  • 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-...
Federico Magallanez's user avatar
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 ...
domotorp's user avatar
  • 18.8k
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 ...
zhaoliang's user avatar
  • 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 ...
Suvrit's user avatar
  • 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 ...
Seva's user avatar
  • 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 ...
მამუკა ჯიბლაძე's user avatar
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$. ...
Sky Cao's user avatar
  • 191
19 votes
1 answer
691 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 $\...
Asvin's user avatar
  • 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
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, ...
Jonah Ostroff's user avatar
19 votes
1 answer
4k views

How should I think about the module of coinvariants of a $G$-module?

Let $G$ be a group, $M$ a $G$-module, then the group of coinvariants is the module $M_G := M/I_GM$, where $I_G$ is the kernel of the augmentation map $\epsilon : \mathbb{Z}G\rightarrow \mathbb{Z}$. ...
stupid_question_bot's user avatar
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)$ ...
M. Lin's user avatar
  • 1,748
19 votes
1 answer
948 views

Recognize this strange expression from linear algebra?

I've come across an odd-looking expression and oh how I wish I had a more elegant description of it. Maybe someone who enjoys symmetric bilinear forms in characteristic two will recognize it? Or ...
Marty's user avatar
  • 13.3k
19 votes
1 answer
904 views

Is the norm of a $0-1$ matrix (almost) attained on a $0-1$ vector?

I'd like to state explicitly a problem which was somehow hidden in my three-week-old post: Does there exist an absolute constant $c>0$ with the property that for any matrix $M\in{\mathcal M}_{m\...
Seva's user avatar
  • 23k
19 votes
1 answer
895 views

Are the only local minima of $\angle(v, Av)$ the eigenvectors?

Let $A$ be an invertible $n \times n$ complex matrix. For $v \in \mathbb{CP}^{n-1}$, define $$d(v) = \frac{|\langle A \tilde{v}, \tilde{v} \rangle |^2}{ \langle A \tilde{v}, A \tilde{v} \rangle \...
David E Speyer's user avatar
19 votes
1 answer
825 views

Number of matrices with given Smith normal form

Denote with $\mathcal{M}$ the set of $(m \times n)$-matrices with integer coefficients bounded by some $K$. Given a matrix $B \in \mathcal{M}$ that is in Smith normal form, is anything known about the ...
Martin's user avatar
  • 1,101