All Questions
614 questions
16
votes
1
answer
3k
views
A property that forces the NORM to be induced by an INNER PRODUCT
Let $(E, \|\cdot\|)$ be a real normed vector space such that for any $a,b\in E$,
$$ \|x +y\|^2 + \|x-y\|^2 \geq 4 \|x\|\cdot \|y\| $$
I want to show that the norm is induced by an inner product. Any ...
16
votes
2
answers
2k
views
How to prove the determinant of a Hilbert-like matrix with parameter is non-zero
Consider some positive non-integer $\beta$ and a non-negative integer $p$. Does anyone have any idea how to show that the determinant of the following matrix is non-zero?
$$
\begin{pmatrix}
\frac{1}{\...
16
votes
6
answers
13k
views
Showing block diagonal structure of matrix by reordering
Suppose we have a block-diagonal matrix $M$, but the block diagonal structure is not immediately apparent from looking at the matrix because the rows/columns are shuffled.
I wish to find a reordering ...
16
votes
5
answers
8k
views
Which graphs have incidence matrices of full rank?
This is a follow-up to a previous question. What graphs have incidence matrices of full rank?
Obvious members of the class: complete graphs.
Obvious counterexamples: Graph with more than two ...
16
votes
1
answer
2k
views
Overlapping Gershgorin disks
We all know Gershgorin's Circle Theorem, which I will summarise for convenience. Let $A=(a_{ij})$ be an $n\times n$ complex matrix. Define the disks $D_1,\ldots,D_n$ by $$D_i = \Bigl\{ z : |z-a_{ii}|\...
16
votes
1
answer
818
views
Lift chain complex from $\mathbb{F}_2$ to $\mathbb{Z}$
We start with a finite dimensional chain complex over $\mathbb{F}_2$, equipped with a basis. That is, we have finitely many finite dimensional $\mathbb{F}_2$-vector spaces $C_0,\dots,C_k$ with bases $...
16
votes
2
answers
905
views
Eigenvalues of an "oblique diagonal" matrix
I am looking for guidance about the behavior of powers of a particular matrix (call it $A_n$ for $n\ge2$), which has come up in a counting problem about quantum knot mosaics (a good reference for ...
15
votes
1
answer
1k
views
Free subgroups of $\mathrm{GL}(2,\mathbb{Z})$
Is there a bound $B$ such that every 2-generator subgroup
$G = \langle a, b \rangle \le {\rm GL}(2,\mathbb{Z})$
whose generators do not satisfy a relation of length $\leq B$ is free?
If it exists, ...
15
votes
5
answers
18k
views
Proving "almost all matrices over C are diagonalizable".
This is an elementary question, but a little subtle so I hope it is suitable for MO.
Let $T$ be an $n \times n$ square matrix over $\mathbb{C}$.
The characteristic polynomial $T - \lambda I$ splits ...
15
votes
1
answer
578
views
Matrix with small elements and prescribed determinant
Let $p$ be a large prime number. I want a $k\times k$ matrix with determinant $p$ and bounded integer elements (say, from -100 to 100). For which minimal $k$ such a matrix does always exist? We can ...
15
votes
2
answers
1k
views
Positive quadratic polynomial
Let $S$ be solutions of a system of quadratic polynomials on $\mathbb{R}^n$.
Suppose $q$ is another quadratic polynomial such that $q|_S\geqslant 0$.
Is it possible to find a polynomial $\tilde q$ ...
15
votes
2
answers
7k
views
Efficient rank-two updates of an eigenvalue decomposition (or more generally SVD)
Let $A$ be a symmetric matrix with eigenvalue decomposition $UDU^T$. Golub, et al.1 and Bunch, et al.2 have shown that given such an $A$, the eigenvalue decomposition of $A+\rho xx^t$ may be computed ...
15
votes
1
answer
649
views
On minimal eigenvalue
Is it true that $\min\left(\lambda_{\min}(M_{12}),\lambda_{\min}(M_{13}),\lambda_{\min}(M_{23})\right) \le \frac{7}{20}$ where $M_{ij}$ is the matrix obtained by selecting the entries at the ...
15
votes
2
answers
6k
views
Linearly constrained eigenvalue problem
Suppose I'd like to:
\begin{align}
\mathop{\text{min}}_\mathbf{x} && \mathbf{x}^T\mathbf{A}\mathbf{x} \\
\text{subject to:} && \mathbf{x}^T \mathbf{M} \mathbf{x} = 1\\
&& \...
15
votes
1
answer
1k
views
Existence of double eigenvalue
Let $A$ and $B$ be complex $4\times 4$ matrices. Assume both are Hermitian, and that they are linearly independent.
Must there exist a nonzero real linear combination $aA + bB$ which has a repeated ...
15
votes
2
answers
793
views
Invariants and orbits of $n$-tensors
My question may be absolutely elementary and is probably answered in 19th century. A reference or a short clear argument would be highly appreciated.
Let $V_1, \ldots V_n$ be finite dimensional ...
15
votes
1
answer
857
views
Symbols of elliptic operators
First let me state the problem, then I'll explain its origin and finally, I'll ask the main question..
Problem S. Fix a positive integer $n$. Find all the pairs $(V, S)$, whith the following ...
15
votes
4
answers
1k
views
Determining if some permutation of a vector satisfies a system of linear equations
Let $A$ be a matrix and $x$ a fixed vector. How can we determine whether or not there exists a permutation matrix $P$ such that $APx=0$? Does this problem reduce to anything well-understood?
15
votes
1
answer
418
views
Conceptual explanation for curious linear-algebra fact in characteristic $2$
All matrices and vectors in this post have entries in the field $\mathbb{F}_2$.
Fix some $n \geq 1$. For an $n \times n$ matrix $X$, write $X_0$ for the column vector whose entries are the diagonal ...
15
votes
4
answers
2k
views
More than $n$ approximately orthonormal vectors in $R^n$
This question was asked at math.stackexchange, where it got several upvotes but no answers.
It is impossible to find $n+1$ mutually orthonormal vectors in $R^n$.
However, it is well established that ...
15
votes
1
answer
2k
views
Necessary and sufficient conditions for a sum of idempotents to be idempotent
Given: a finite list of $n$-by-$n$ idempotent complex matrices $E_1, E_2, \ldots, E_k$.
If all pairwise products $E_i E_j$ (with $i \neq j$) are zero, it is trivial to show the sum $E_1 + E_2 + \cdots ...
15
votes
3
answers
5k
views
How to show a certain determinant is non-zero
For any $n$ distinct points $x_1,x_2 , \ldots , x_n$ on the real line show that
the matrix $M$ where $M(i,j) = e^{\lambda_j x_i} $ has non-zero determinant
where $\lambda_1 \lt \lambda_2 \lt \ldots \...
14
votes
1
answer
4k
views
Do these matrix rings have non-zero elements that are neither units nor zero divisors?
First, a disclaimer: This is a repost of a question I asked on stackexchange (no answer there).
Let $R$ be a commutative ring (with $1$) and $R^{n \times n}$ be the ring of $n \times n$ matrices with ...
14
votes
3
answers
872
views
How can we realize different combinatorial objects as the dimension of a construction on vector spaces? Are the resulting algebras useful?
Fix a vector space $V$ of dimension $n$ over some field $F$. Here are three commonly seen constructions:
its $k$th tensor power, $T^kV$, which has dimension $n^k$
its $k$th exterior power, $\Lambda^k(...
14
votes
2
answers
655
views
Number triangle
This question arose just out of curiosity. Note the triangle of 0-1's below, whose construction is as follows. Choose any number, say 53 as done here. The first line of the triangle is the binary ...
14
votes
1
answer
416
views
Lipschitz property of the determinant
$\newcommand{\A}{\mathcal A}\newcommand{\Tr}{\operatorname{tr}}$For $c$ and $C$ such that $0<c<C<\infty$, let $\A_{d;c,C}$ denote the set of all symmetric positive-definite real $d\times d$ ...
14
votes
0
answers
602
views
Is the Zariski density proof of Cayley-Hamilton circular?
This old MO thread and its comments contains a discussion of the Zariski density proof of Cayley-Hamilton (I have also asked a separate question about the proof Victor gives in the comments here). ...
14
votes
1
answer
581
views
How flexible is the infinite-dimensional torus?
Let $\mathbb T=\mathbb R/\mathbb Z$ be the circle group and $\mathbb T^\omega$ be the infinite-dimensional torus, considered as an abelian compact topological group.
Problem 1. Is it true that for ...
14
votes
3
answers
3k
views
Diagonalizing a Certain Real and Symmetric Toeplitz Matrix
Consider $0\leq \alpha\leq 1$, and let $A_{\alpha}$ be the Toeplitz $n\times n$ matrix given by
$$
A_\alpha := \begin{bmatrix}
1 & \alpha & \alpha^2 & \ldots &\alpha^{n-1} \\\
\alpha ...
13
votes
2
answers
946
views
Computing a large permanent
Is there a practical way to compute the permanent of a large ($91 \times 91$) $(0,1)$ matrix?
I have tried to use the matlab function written by Luke Winslow which works great for smaller matrices ...
13
votes
1
answer
625
views
A difficult determinant
(EDIT: I have removed the denominators I had in a previous version as they were superfluous)
The $N\times N$ determinant
$$D(a,\vec{b})=\det\left((2N+a+b_j-i-j)!\right)$$
has the nice form
$$D(a,\...
13
votes
2
answers
1k
views
Action of SL(2,Z) on upper triangular primitive integer matrices of determinant N, from the right. Is it transitive?
I am porting this question across from StackExchange, since it has received no answers and perhaps is sufficiently deep to fit here.
I am considering the set of upper triangular matrices
$$D_N=\left\...
13
votes
1
answer
468
views
Near-linear mappings from $\mathbb F_p$ to $\mathbb R$
$\newcommand{\F}{{\mathbb F}}$
$\newcommand{\R}{{\mathbb R}}$
$\renewcommand{\phi}{\varphi}$
Let $p\ge 5$ be a prime.
If the functions $\phi_1,\phi_2,\phi_3\colon\F_p\to\R$ satisfy $\phi_1(x)+\...
13
votes
1
answer
2k
views
Banach-Mazur distance between $\ell^p$-norms
Let $E^n$ be the real or complex space of dimension $n$. If $N$ and $M$ are two norms over $E^n$, and if $A$ is an endomorphism, then
$$\|A\|^M_N:=\sup_{x\ne0}\frac{M(Ax)}{N(x)}$$
is an operator norm ...
13
votes
4
answers
3k
views
Multivariate analogue of Vandermonde determinant
Dear all,
Consider the $(n+1)\times (n+1)$ matrix $A$ with indeterminates $X_i, Y_i$, $0\leq i\leq n$ such that the $(i,j)$-th entry is given by $X_i^jY_i^{n-j}$. The $i$-th row is $(X_i^n,X_i^{n-1}...
13
votes
3
answers
746
views
Is there a row vector $x$ with integer entries such that no entry of $xM$ is $0 \text{ (mod }p\text{)}$?
Let $p$ be a prime and let $M$ be an $n \times m$ matrix with integer entries such that $M\vec{v} \not\equiv \vec{0} \text{ (mod }p\text{)}$ for any column vector $\vec{v} \neq \vec{0}$ whose entries ...
13
votes
1
answer
1k
views
A generalization of the Powers-Stormer inequality
The well-known Powers-Stormer inequality says the following: for positive semidefinite operators $A, B$, we have that $\mathrm{Tr}((A - B)(A - B)) \leq \| A^2 - B^2 \|_1$, where $\| \cdot \|_1$ ...
13
votes
1
answer
311
views
Permanent of the Coxeter matrix of a distributive lattice
Let $L$ be a finite distributive lattice with $n$ elements. Let $C=(c_{x,y})$ be the $n \times n$ matrix with entry 1 in case $x \leq y$ and 0 else.
The Coxeter matrix of $L$ is defined as the matrix $...
13
votes
2
answers
913
views
Almost Hadamard matrices
As well-known, a Hadamard matrix is a square matrix with all coefficients $\pm 1$
and pairwise orthogonal rows or columns. Such matrices exist conjecturally
in every dimension divisible by $4$. Call ...
13
votes
2
answers
6k
views
Parametrization of positive semidefinite matrices
We know that a real, symmetric, positive definite matrix $A$ of size $n\times n$ can be parametrized by a vector $\theta$ of $\frac{n(n+1)}{2}$ parameters thanks to the Cholesky decomposition:
$$
A = ...
13
votes
4
answers
3k
views
subspaces of singular matrices
Let $A$, $B$ be square matrices over infinite field (we identify them with linear operators on the vector space of columns). It is given that for all scalars $a,b$ the matrix $aA+bB$ is singular. Does ...
13
votes
1
answer
1k
views
An inequality for the spectral radius of matrices used by J. Bochi
I am interested in the history of an inequality for the spectral radius of a $d\times d$ real or complex matrix, which occurs in Jairo Bochi's 2002 article Inequalities for numerical invariants of ...
12
votes
5
answers
3k
views
How can I learn about doing linear algebra with trace diagrams?
There is a wikipedia article. There is a paper by Elisha Peterson. I tried reading these but they don't seem to click for me.
Are there books or other resources for learning how to do linear algebra ...
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 ...
12
votes
3
answers
2k
views
Representability of matroids over $\mathbb R$
Let $M$ be a matroid, for example viewed as being given by a finite set $X$ and a rank function $d : P(X) \to {\mathbb N}$ such that
1) $d(\varnothing)=0$, $d(\lbrace x \rbrace)=1$, for all $x \in X$,...
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 ...
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{...
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 ...
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 ...
12
votes
3
answers
1k
views
Conjugacy in $GL(n,\mathbb Z)$
How can I determine whether $A_1,A_2\in GL(n,\mathbb Z)$ conjugate in $GL(n,\mathbb Z)$ and if they are, how can I find a $P\in GL(n,\mathbb Z)$ for which $A_2 = P^{-1}.A_1.P$ ?
In $GL(n,\mathbb Q)$ ...