Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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 ...
user avatar
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}{\...
Ahmadreza Momeni's user avatar
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 ...
Szabolcs Horvát's user avatar
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 ...
Jiahao Chen's user avatar
  • 1,890
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}|\...
Brendan McKay's user avatar
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 $...
Sucharit Sarkar's user avatar
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 ...
Russell May's user avatar
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, ...
Stefan Kohl's user avatar
  • 19.6k
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 ...
Anweshi's user avatar
  • 7,442
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 ...
Fedor Petrov's user avatar
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$ ...
Anton Petrunin's user avatar
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 ...
Lepidopterist's user avatar
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 ...
Jasmine's user avatar
  • 178
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\\ && \...
Alec Jacobson's user avatar
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 ...
Nik Weaver's user avatar
  • 42.8k
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 ...
Bugs Bunny's user avatar
  • 12.3k
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 ...
Liviu Nicolaescu's user avatar
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?
Jack M's user avatar
  • 623
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 ...
Alice's user avatar
  • 255
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 ...
Nick Alger's user avatar
  • 1,160
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 ...
Gene Herman's user avatar
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 \...
smilingbuddha's user avatar
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 ...
Bill Cook's user avatar
  • 1,197
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(...
Zev Chonoles's user avatar
  • 6,792
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 ...
DSM's user avatar
  • 1,216
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$ ...
Iosif Pinelis's user avatar
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). ...
Qiaochu Yuan's user avatar
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 ...
Taras Banakh's user avatar
  • 41.8k
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 ...
ght's user avatar
  • 3,626
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 ...
Felix Goldberg's user avatar
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,\...
Marcel's user avatar
  • 2,552
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\...
Haden Spence's user avatar
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)+\...
Seva's user avatar
  • 23k
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 ...
Denis Serre's user avatar
  • 52.3k
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}...
Zeyu's user avatar
  • 537
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 ...
Analysis Student's user avatar
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$ ...
Henry Yuen's user avatar
  • 2,019
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 $...
Mare's user avatar
  • 26.5k
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 ...
Roland Bacher's user avatar
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 = ...
epsilone's user avatar
  • 313
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 ...
Fedor Petrov's user avatar
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 ...
Ian Morris's user avatar
  • 6,206
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 ...
Kim Greene's user avatar
  • 3,613
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 ...
Wolfgang's user avatar
  • 13.4k
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$,...
Andreas Thom's user avatar
  • 25.5k
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 ...
Noah Schweber's user avatar
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{...
Tobi's user avatar
  • 121
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 ...
lino's user avatar
  • 253
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 ...
Alec Jacobson's user avatar
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)$ ...
Wox's user avatar
  • 347

1
3 4
5
6 7
13