All Questions
6,289 questions
9
votes
1
answer
1k
views
(Elementary?) combinatorial identity expressing binomial coefficients as an alternating sum over permutations.
Background
I came up with this while trying to find a sort of high-level exposition of the exterior algebra of a vector space. Let $V$ be a vector space of dimension $n$ over $\mathbb{C}$, and let $...
- 8,559
6
votes
2
answers
2k
views
Efficient approximation of a matrix and its inverse
Assume that $ A $ is a real $ n\times n $ matrix whose rows constitute an orthonormal basis of $ \mathbb R^n $.
Informal statement of question: Assume we want to approximate $ A $ by a rational ...
- 201
6
votes
2
answers
8k
views
Existence/Uniqueness of Nonnegative Solutions of Linear Systems of Equations
Suppose we have an $m$x$n$ matrix $A$, with $m\lt n$, and an $m$x$1$ vector $b$. Are there existence and uniqueness conditions characterizing nonnegative solutions of the system of linear equations $...
3
votes
0
answers
2k
views
Eigenvalue Problems with Linear Constraints
The motivation for this problem comes from trying to develop a simple way to decompose domains into non-overlapping subdomains to solve for the eigenvalues of some differential operator. The idea is ...
- 543
2
votes
0
answers
4k
views
Eigenvalues of sum of commuting matrices [closed]
With reference to the following thread :
Eigenvalues of Matrix Sums
Answer by Jonas Meyer is as follows :
If 2 positive matrices commute, than each eigenvalue of the sum is a sum of eigenvalues of ...
- 21
1
vote
1
answer
736
views
Matrix Conjugates over Finite Fields
Thinking about Diffe-Hillman for matrices brought me to the following question.
Given $\mathbb{F}_{p^k}$ the finite field with $p^k$ elements when can we find non-trivial solutions to
$\begin{...
- 4,842
61
votes
11
answers
11k
views
Geometric proof of the Vandermonde determinant?
The Vandermonde matrix is the $n\times n$ matrix whose $(i,j)$-th component is $x_j^{i-1}$, where the $x_j$ are indeterminates. It is well known that the determinant of this matrix is $$\prod_{1\leq ...
- 23k
3
votes
2
answers
375
views
Invariant subspaces of subalgebras of $M_n(C)$
Given a subalgebra E of $M_n$ (nxn complex valued matrices), what can we say about the subspaces F of $M_n$ such that $EF \subset F$? Googling for an answer gives me the reference:
Israel Gohberg, ...
- 243
4
votes
1
answer
548
views
O(n^2) algorithm to approximate the sum of the log of the singular values of a matrix
Given an $M \times N$ matrix of rank $N$ ($M \ge N$) with $i^{th}$ singular value $\sigma_i$, does their exist an $O(M^2)$ algorithm for approximating the sum $ H =\sum_{i=1}^N \log(\sigma_i)$ with ...
- 188
7
votes
5
answers
2k
views
Explicit invariants (under change of basis) of maps $V \to V \otimes V$.
It is standard to construct numbers associated to a linear transformation $f: V \to V$ of a finite-dimensional vector space which are invariant under change of basis. The coefficients of the ...
- 4,990
1
vote
1
answer
715
views
Find a matrix's nullspace from submatrix nullspace
This is probably a basic question, but my linear algebra is weak.
Suppose I want to compute the nullspace of a matrix A using some iterative method (e.g. Lanczos). Suppose further that I know a ...
9
votes
2
answers
2k
views
Jordan Form Over a Polynomial Ring
Let $X$ be the set of $k\times k$ matrix with entries in $\mathbb{C}$, and let $M\in X$. The group $GL(k,\mathbb{C})$ acts on $X$ by conjugation, and according to the Jordan decomposition theorem (...
- 2,087
2
votes
1
answer
810
views
On matrices that almost have the same eigenvalues
Let $A$ and $B$ be two $4\times 4$ matrices. Using Newton's identities, one can prove that if
$$\det(A) = \det(B)\quad \text{and}\quad \mathrm{tr}(A^i) = \mathrm{tr}(B^i)$$ for $i=1,2,3$, then $A$ and ...
- 2,154
3
votes
1
answer
632
views
What is the entropy of a density matrix which is the sum of two unitarily equivalent projectors?
Construction
Suppose I have a density matrix $\rho$ which is proportional to a projector $P$ formed by tensoring together $N$ small projectors $P^{(i)}$ of rank 2:
$P^{(i)} = |a\rangle_i\langle a| + |...
- 846
1
vote
2
answers
917
views
Any known compact expression for
Is there any known compact expression for the sum
$$S_{k} = \sum_{i=1}^{k} A^{i-1} P Q^{k-i}$$
where $A$, $P$ and $Q$ are respectively $m \times m$, $m \times n$ and $n \times n$ matrices?.
You can ...
- 61
4
votes
1
answer
866
views
When is a triangular matrix totally unimodular?
I have a {0,1}, invertible, triangular matrix, that I would like to show is totally unimodular. Are there any known results on the total unimodularity of classes of triangular matrices?
- 1,182
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
-4
votes
2
answers
6k
views
Factorizing polynomials of several variables (in a different perespective)
I am looking for factorization of polynomials of several variables in the way outlined below.
Consider a second degree polynomial of two variables over the complex numbers.
"P(x,y) = Ax^2 + Bxy + Cy^...
1
vote
1
answer
356
views
Finding the $J$ for a symplectic vector space
I found something strange when I was working on some other problems.
I thought the triple intersection description of the unitary group said that any two of $(g, \omega, J)$ determines the third ...
- 1,525
6
votes
1
answer
778
views
Inverse function theorem for DC-functions
I would like to have an inverse (or/and) implicite function theorem for DC-functions.
It seems that I have right definitions, but I fail to prove it...
Definitions:
Let $h:\mathbb R^n\to\mathbb R$ ...
- 45k
11
votes
1
answer
688
views
Existence of a pair of matrices in SL(2,Z) satisfying certain constraints on the spectral radius
Some background: my coauthors and I are working on a problem which deals with the exponential growth rates of certain infinite products of matrices. One of the sub-problems which arises in this ...
- 6,206
2
votes
0
answers
5k
views
A system of linear equations with linear constraints
Mathematical problem.
Suppose we have $2n$ indeterminates $x_1,\dots,x_n$ and $y_1,\dots,y_n$ (which are denoted by $q$ with indices and called abundances below) and $m$ subsets $P_1,\dots,P_m$ of $\...
14
votes
2
answers
937
views
Involutions in GL_n(Z)
Is there a classification of involutions in $\text{GL}_n(\mathbb{Z})$?
Here's some more details about what I mean. Consider $f \in \text{GL}_n(\mathbb{Z})$ such that $f^2=1$. Regard $f$ as an ...
- 245
8
votes
2
answers
3k
views
Centralizers in GL(n,p)
There appear to be a number of rational canonical forms. The best thing about standards is how many there are to choose from. However, the standard I choose seems to have a centralizer that is ...
- 10.7k
4
votes
0
answers
790
views
Is it possible to use linear programming to solve this problem?
I am trying to write software to minimize pricing for cell phone subscription services, ie: choose the optimum plan for each customer in a large group.
Could someone comment on whether this is ...
- 41
13
votes
4
answers
2k
views
Rational congruence of binomial coefficient matrices
Skip Garibaldi asks if there is an elementary proof of the following fact that "accidentally" fell out of some high-powered machinery he was working on.
Say that two matrices $A$ and $B$ over the ...
- 82.7k
4
votes
2
answers
1k
views
Simultaneous Block decomposition of a set of orthogonal projections
An orthogonal projection is an Hermitian matrix $P$ such that $P^2=P$.
Denote $U^*$ the conjugate transpose of a matrix $U$.
It can be easily shown that for two projections $P_1$ and $P_2$, there ...
9
votes
3
answers
4k
views
Eigenvectors of a certain big upper triangular matrix
I'm looking at this matrix:
$$
\begin{pmatrix}
1 & 1/2 & 1/8 & 1/48 & 1/384 & \dots \\
0 & 1/2 & 1/4 & 1/16 & 1/96 & \dots \\
0 & 0 & 1/8 & 1/16 &...
2
votes
1
answer
455
views
A question on matrix decomposition.
Is the following claim true?
Claim Let $A, B\in C^{n\times n}$ with $rank(A)=rank(B)=r$. Then there exist nonsingular matrices $P_1, P_2, Q_1, Q_2$ such that
$$ Q_1AP_1=Q_2BP_2=\left(\begin{array}{...
- 1,858
0
votes
2
answers
579
views
Linear algebra inequality
I'm wondering (hoping) if an inequality is true. Please can anyone help me?
Let $V$ be a complex vector space $dim_{\mathbb{C}}(V)=n$
with a hermitian scalar product $h$.
Let $v,a, b \in V$.
Is it ...
- 1,727
12
votes
0
answers
349
views
Matroids with prescribed independent sets
Let $A$ be a finite set. Let $B$ be a family of subsets of $A$. We are interested in a matroid with a minimum rank such that every element of $B$ is independent. The answer is obvious - a uniform ...
- 1,791
15
votes
9
answers
9k
views
Exponential of large matrices
I want to make a diffusion kernel, which involves $e^{\beta A}$, where A is a large matrix (25k by 25k). It is an adjacency matrix, so it's symmetric and very sparse.
Does anyone have a ...
- 151
4
votes
2
answers
16k
views
Submultiplicative matrix norm: Max Norm
Various sources claim that a maximum norm $||A||_{max}=\max_{i,j}|a_{ij}|$ is not submultiplicative, i.e. $||AB||_{max}\not\leq||A||_{max}||B||_{max}$.
Where can I find what norm a,b satisfy $||AB||...
- 93
3
votes
2
answers
2k
views
How can we explicitly find the maximum eigenvalue of a tridiagonal matrix?
I just came across a matrix of the form
$A:=\begin{pmatrix}
0&-\frac{c_0}{b_0}&0&\cdots&0\\-\frac{a_1}{b_1}&0&-\frac{c_1}{b_1}&\cdots&0\\0&-\frac{a_2}{b_2}&0&...
- 93
5
votes
1
answer
745
views
Decide how many non-negative solutions a set of multivariate quadratic equations have
Given a set of multivariate, quadratic, non-homogeneous equations, is there a way to decide how many non-negative roots it have?
Some explanations:
All the coefficients are real numbers.
The number ...
- 183
8
votes
3
answers
414
views
What can be said about pairs of matrices P,Q that satisfies $(P^{-1})^T \circ P = (Q^{-1})^T \circ Q$ ?
Let $P,Q$ be $n$ by $n$ invertible matrices. Suppose further that $P$ and $Q$ satisfies the following equation :
$$(P^{-1})^T \circ P = (Q^{-1})^T \circ Q$$
where $\circ$ denotes the Hadamard matrix ...
- 2,154
3
votes
2
answers
1k
views
"Main" diagonal of a matrix
Hello!
I'm in search of some (possibly statistical) measure for matrices. I want to classify a square matrix as having the largest numbers running along the main diagonal or along the anitdiagonal. ...
- 33
2
votes
0
answers
156
views
A solver of a noisy system containing pairs of very similar linear equations, this is not about accurate solving of ill-cond. s.
Let there be a possibly overdetermined system AX = B, where B are some measured data, with a low noise level. To cancel out the measurement noise, and to allow for more unknowns, a large B is acquired,...
- 21
17
votes
4
answers
10k
views
Prime/undecomposable matrices
Prime matrices as defined in the following paper Prime matrices P. F. RIVETT AND N. I. P. MACKINNON carry over many properties of factorization as in natural numbers to matrices over the field of ...
- 2,855
4
votes
2
answers
734
views
Analyzing the solution to a second-order, non-linear ODE
Let $\psi : [0,\infty] \to \mathbb R$ be a strictly positive, continuously differentiable function, and consider the non-linear ODE $$\ddot x = - \frac{1}{4} \frac{\psi'(x)}{\psi(x)} \left( \dot x^2 - ...
- 8,512
9
votes
2
answers
2k
views
Classification of adjoint orbits for orthogonal and symplectic Lie algebras?
This might be standard, but I have not seen it before:
Let $K$ be an algebraically closed field (of characteristic 0 if necessary). Let $G$ be the orthogonal group ${\bf O}(m)$ or the symplectic ...
- 10.7k
2
votes
3
answers
806
views
An Linear Algebra Inequality
How to prove the following inequality:
Let $X$ and $Y$ be $n\times m$ matrices with real entries. Prove that
\begin{equation}
\det\left(XY^T\right)^2 \leq \det\left(XX^T\right)\det\left(YY^T\right) .
\...
- 31
7
votes
2
answers
505
views
The set of non-smooth points of a convex function is (m - 1)-rectifiable
I am looking for a reference to the following result.
Let $f:\mathbb R^m\to\mathbb R$ be a convex function.
Then $f$ is differentiable at all points of outside of a countable union of $(m-1)$-...
- 45k
13
votes
2
answers
8k
views
AC in group isomorphism between R and R^2
Using the axiom of choice, one can show that $\mathbb{R}$ and $\mathbb{R}^2$ are isomorphic as additive groups. In particular, they are both vector spaces over $\mathbb{Q}$ and AC gives bases of ...
- 8,491
2
votes
1
answer
987
views
Surjectivity of bilinear forms.
It is not uncommon to describe interesting classes of field extensions by declaring that an extension $L|K$ belongs to that class if some type of problem with $K$-coefficiens has a property over $L$ ...
- 4,015
12
votes
2
answers
2k
views
(Path) connected set of matrices?
Let $N \in \mathfrak{M}_n(\mathbb{C})$ nilpotent, such that there exists $X \in \mathfrak M_n(\mathbb{C})$ with $X^2=N$ (take for instance $n>2$ and $N(1,n)=1$; $N(i,j)=0$ otherwise).
Denote by $\...
- 2,829
5
votes
1
answer
3k
views
Finite subgroups of GL_n(C)
A finite groups of $\mathrm{GL}_n(\mathbb C)$ of exponent $m$ necessarily have order $C$ verifying $C\leqslant m^n$ and $n! m^n$ divides $C$, but this condition is not sufficient, for instance $\...
- 2,829
2
votes
3
answers
1k
views
Problem with the proof of a corollary of Schur's lemma
I'm reading the book 'A course in Modern Mathematical Physics' by
'Szekeres' and encountered a problem in interpreting the proof of the
following corollary of Schur's lemma.
The corollary and the ...
- 81
2
votes
3
answers
2k
views
free Z-modules: Bases etc.
I need a reference which states which of the "normal properties of vector spaces" carry over to free $\mathbb{Z}$-modules.
Especially I am interested in things like: If you have a linear map between ...
- 1,282
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