All Questions
6,288 questions
2
votes
0
answers
187
views
Recovering a linear map from a non-linear approximation
The problem described here is algorithmic. We are given "black box access" to a map $f:R^d\to R^d$. By this we mean that one may query the value of $f(v)$ for an arbitrary $v\in R^d$.
We assume that ...
7
votes
1
answer
596
views
Eigenvalues of $A^2+B^2$ from those of $A$, $B$ and $A+B$
This question comes from a colleague working in econometrics. $A$ and $B$ are $n\times n$ real symmetric matrices. If we know the eigenvalues of $A$, $B$ and $A+B$, what meaningful information can we ...
- 1,981
3
votes
1
answer
621
views
Largest eigenvalue of a periodic Jacobi matrix
There is a vast literature on Jacobi matrices, I just don't know where to start looking. I'm interested in estimating the largest eigenvalue of the $n\times n$ periodic Jacobi matrix $D+P+P^{-1}$, ...
- 11.1k
2
votes
3
answers
5k
views
Gordan's Theorem with $Ax=b$
Is there a version of Gordan's Theorem in which $Ax=0$ has been replaced by $Ax=b$? That is, I want a condition (possibly including conditions on $A$) for when $Ax=b$ has a solution $x \neq 0$, for $A ...
- 491
53
votes
7
answers
51k
views
Determinant of sum of positive definite matrices
Say $A$ and $B$ are symmetric, positive definite matrices. I've proved that
$$\det(A+B) \ge \det(A) + \det(B)$$
in the case that $A$ and $B$ are two dimensional. Is this true in general for $n$-...
- 541
3
votes
3
answers
993
views
Matrix decomposition the other way
First of all, this is no useful way to decompose a matrix -
you need to know the eigenvalues beforehand. But it popped up
naturally during my knot theory dabblings.
Assume that you know the ...
- 4,829
0
votes
1
answer
340
views
[Matrices over Z] - An algorithm for calculating the diagonal with elementary operations
Dear mathoverflow,
Let
$
\left(
\begin{array}{cc}
a & b \newline
c & d
\end{array}
\right)
$
be a matrix with $a, b, c, d \in \mathbb{Z}$, $\gcd(a,b,c,d) = 1$ and $ad - bc = \pm N$, with $N &...
- 11
10
votes
5
answers
8k
views
Shifted QR algorithm—why does the shift help?
I read that a way to speed up the convergence rate of the QR algorithm is to shift the target
matrix. It is not so clear to me why this helps. The convergence rate depends on the
minimum gap between ...
- 353
8
votes
0
answers
451
views
integral matrix of order p
Hi everyone
Let $p$ be a prime number. I am interested to classify $\{ A\in {\rm GL}_{p-1}(\mathbb{Z}): {\rm ord}(A)=p \}$ up to conjugacy. One reason to consider this problem is its relation to ...
- 2,508
3
votes
1
answer
901
views
spectral theorem for infinite-dimensional matrices
Keller and Ochsenius (1995) has a spectral theorem for finite-dimensional symmetric matrices over the field of formal power series with real coefficients $\mathbf{R}((t))$ (they actually have a more ...
- 480
15
votes
3
answers
6k
views
Questions on Toeplitz matrices: invertibility, determinant, positive-definiteness
These questions are probably very basic but I'll dare to ask them anyway since I didn't have much luck in Math Stack Exchange.
Let $A$ be an $n \times n$ Hermitian Toeplitz matrix:
$$A = \begin{...
- 3,626
4
votes
0
answers
300
views
Field of Values and Eigenvalues
Let $A$ be an $n \times n$ matrix. Define the field of values of $A$, denoted $W(A)$, as
$ W(A) := \{c \in \mathbb{C} : \exists x \in \mathbb{C}^n, \|x\|_2 = 1, x^H Ax = c \} $
The question is, ...
- 316
7
votes
2
answers
2k
views
When is this map completely positive?
Consider the complex $n$-by-$n$ matrices $M_n$.
Suppose that $A_i$, for $i=1,\ldots,n^2$, satisfy $\mathrm{Tr}(A_i^*
A_j)=\delta_{ij}$, so that together they form an orthonormal basis for
$M_n$. ...
- 3,937
6
votes
2
answers
520
views
Upper bounds on the permanent of dense 0-1 matrix
I am looking for some result useful in deriving following (conjecture?):
Let $A$ be an $n\times n$ matrix with $0-1$ entries.
Suppose, that exactly $k\leqslant n$ entries are equal to $0$.
Then $\...
- 696
10
votes
2
answers
1k
views
Indecomposable vector spaces and the axiom of choice
It is a known result by A. Blass that the axiom of choice is equivalent to the assertion that every vector space has a basis. (Rubin's Equivalents of the Axiom of Choice: form B)
It is also known ...
- 39.8k
0
votes
1
answer
824
views
Non-zero diagonal through permutation of rows
I'm looking for a reference of the following statement (which can easily be proved by Laplace's formula and induction):
Let $R$ be a commutative ring with
identity and let $A$ be an invertible
...
- 16.2k
1
vote
2
answers
262
views
How to approx. decompose a sym. p.d. matrix M into X'X?
M: pxp symmetric p.d. matrix with unit diagonals
n: number much smaller than p
Want a nonrandom nxp matrix X such that X'X is
close to M element-wise. If n gets larger, hopefully
difference ...
- 21
2
votes
0
answers
505
views
Ideal membership
Let $n=2t$ be an even number. Let $F$ denote a finite field where
$|F|=q$. Let $A_{1}, A_{2},\ldots, A_{t}$ and
$B_{1},B_{2},\ldots,B_{t}$ be distinct matrices in $M_{n}(F)$. Let
$$ X =
\begin{...
- 461
1
vote
2
answers
354
views
Does this norm inequality hold for projections onto the range of a sum of matrices?
Although it's simply stated, this is neither a homework problem or trivial (I think, but I'd be happy to be proven wrong :) ).
Let $A,B$ be matrices and $x$ be a vector. Is it true that
$$ \|P_{A+B} ...
- 922
8
votes
2
answers
870
views
A Linear Algebra Question
Let $M$ be a symmetric square matrix with integer coefficients and $M_k$ the matrix obtained by deleting the k-th line and k-th column. If det(M)=0 does it follow that $\det(M_kM_j)$ is a square?
- 81
5
votes
1
answer
528
views
Completely bounded maps on Mn
The aim of this question is to collect nice maps on $M_n(\mathbb{C})$ with the following property:
$\phi_n:M_n(\mathbb{C})\rightarrow M_n(\mathbb{C})$ with $||\phi||=1$ and $||\phi_n||_{cb}\...
- 4,705
4
votes
1
answer
7k
views
Matrix optimization problem
This is (probably) an easy one:
Given a positive definite matrix $M$, find the positive definite matrix $X$, which minimizes $\textrm{tr}(X M)$ subject to $\det(X) = 1$.
Looking for how to find X, ...
- 379
8
votes
2
answers
1k
views
On positive matrices and their eigenvectors
Let $A$ be an $n\times n$ positive integer-valued matrix, that is every entry of $A$ is a a positive integer. Let $\lambda$ be the Perron-Frobenius eigenvalue and $x = (x_1,...,x_n)^T$ the ...
- 351
2
votes
0
answers
279
views
Eigenvectors of convolution with a normal distribution over a restricted interval
Suppose I have a random variable $X_0$ with a p.d.f $f_0$ supported on the real interval $[a_0, b_0]$. $X_1$ is the restriction to $[a_1, b_1]$ of the sum $X_0 + g$, where $g$ is normally distributed $...
- 1,902
3
votes
1
answer
303
views
ABA-product of matrices and length of chains of principal inner ideals
Let $k$ be a field, $p,q$ positive integers, and let $R$ be the space of $(p \times q)$-matrices over $k$, and $S$ be the space of $(q \times p)$-matrices over $k$. For every matrix $A \in R$, we ...
- 6,614
3
votes
1
answer
1k
views
On matrix representations of the Clifford algebras of type $Cl(0,n)$
Can matrix representations of clifford algebras of type Cl(0,n) be found? Specifically for even orders
- 33
6
votes
1
answer
2k
views
Matrices that are Hadamard products of $X$ and $X^{-T}$
What are the matrices that you can write in the form $X \odot X^{-T}$, for a complex square matrix $X$, where $X^{-T}$ is the inverse of the complex transpose (not conjugate) and $\odot$ is the ...
- 20.2k
9
votes
4
answers
2k
views
Is there a useful generalization of the Schmidt decomposition to the tensoring together of 3 or more vector spaces?
I've rewritten the question in math notation, and I've left the old version in physics bra-ket notation here.
Background
A simple consequence of the singular value decomposition is that any vector $...
- 846
3
votes
0
answers
474
views
Jacobson-Bourbaki correspondence
The Jacobson-Bourbaki correspondence induces the traditional, finite Galois correspondence by suitable restriction; I've been pondering two things: 1. Are there any (other) interesting applications of ...
3
votes
0
answers
473
views
Infinite Galois correspondence "according to Artin"
Ever since Artin's lectures on Galois Theory one knows how to set up and derive the usual Galois correspondence in the finite(-dimensional) case using just a bit of elementary Linear Algebra, and ...
2
votes
1
answer
394
views
regarding metric and symplectic forms
Let $g$ be a positive definite symmetric form on a $2n$-dimensional vector space (a metric), $\mathbb{J}$ the symplectic unit and $c$ a real number. Define the symmetric form
$h = g + c[g,\mathbb{J}],...
- 503
8
votes
3
answers
6k
views
Is there a fast way to compute matrix multiplication mod $p$?
I think people have some general strategy to do matrix multiplication fast. But what about for the finite field of $p$ elements? (e.g. when $p=2$, one should have some faster way.)
So my question is, ...
- 3,806
4
votes
0
answers
155
views
Special linear group of a quotient
Let J be a non-trivial ideal of a commutative ring A. The canonical map from A to the quotient A/J induces a homomorphism $\varphi : SL_n(A) \to SL_n(A/J)$. In general $\varphi$ is not surjective (for ...
- 229
3
votes
2
answers
707
views
$k$ structures on $K$ vector spaces
The following statement is made in Borel's Linear Algebraic groups, section 11 on $k$ structures.
Let $V$ and $W$ be $K$ vector spaces with $k$ structures. If $f:V\to W$ is $K$ linear, then $f$ is ...
- 1,563
12
votes
0
answers
603
views
On a tentative generalization of the Schmidt decomposition
Background
I am a PhD student in Physics and I am currently developing quite refined computer codes that allow to simulate many-body quantum systems living on a lattice. The difficulty resides in ...
- 141
4
votes
1
answer
1k
views
An optimization problem in numerical linear algebra
Provided two diagonal real matrix which has positive entries, $V$ and $U$.
Find a real matrix $A$, satisfying $A^TA=a^2I$ for some scalar $a$, to minimise
$\left|A^TVA-U\right|\quad\quad(*)$ ...
- 135
10
votes
4
answers
2k
views
How to solve Ax=b incrementally ?
Hi, everyone.
What I am struggling is the following problem. I have a linear matrix equation $Ax=b$, where $A$ is a known $n \times n$ large sparse real matrix, $x$ and $b$ are known $n \times 1$ ...
- 101
1
vote
2
answers
3k
views
Fast algorithms for computing nullspace of a positive semidefinite matrix over Z
Let $A \in \mathbb{Z}^{n \times n}$ be a positive semidefinite sparse matrix. I am looking for asymptotically fast algorithms for computing the nullspace basis of $A$ (or just random elements in the ...
- 236
2
votes
4
answers
2k
views
Efficient algorithm for finding the minima of a piecewise linear function
Consider real numbers $a_i$ and $b_i$ for $i=1\dots n$ and define a function by
$f(x) = \max_i ( a_i + b_i x )$
We desire to find $\min_x f(x)$. Obviously this occurs at an intersection of two lines:...
- 823
2
votes
0
answers
292
views
Seeking the normalizing constant (or any references) for a distribution over a subset of positive definite martrices
I'm interested in a probability distribution over the set of positive definite matrices with unit diagonal elements. That is, and $X$ such that:
$X \in S^{n+}, \forall_{i}X_{ii} = 1$ where $S^{n+}$ ...
- 379
6
votes
4
answers
15k
views
how to find one column or one entry of the matrix inversion
Let $A$ be a square $n \times n$ matrix, which is invertible. Now we want to find the $i$-th column of $A^{-1}$ and one $(i,j)-$ entry of $A^{-1}$. Is there any way to compute only a small of portion ...
- 61
8
votes
1
answer
646
views
Projecting the unit cube onto a (very special) subspace
Let $n>1$ be an integer, and $a>1$ a real number. Consider the subspace $L<R^{2^n}$ generated by the $n$ possible tensor products of the $n-1$ copies of the vector $(1,a)$ and one copy of $(a,...
- 23k
3
votes
0
answers
311
views
what is the largest gap between rank and approximate rank
$\epsilon$-approximation rank of a matrix $M$ is the minimum rank of a real matrix $A$ which differs from $M$ at most $\epsilon$ in each entry. Associating any function $f:X\times Y\rightarrow${1,-1} ...
- 363
2
votes
3
answers
3k
views
invertability of a matrix [closed]
Hi all,
I heard a claim that if I have a matrix $A\in\mathbb R^{n\times n}$ such that $A^n \to 0 \ (\text{for }n\to\infty )$
(that is, every entry of $A^n$ converges to $0$ where $n\to \infty$)
then ...
- 23
0
votes
1
answer
152
views
"locally" factoring subgroups of Lie groups
I'm not really a math person, and apologize if the question here is too simple. I've ended up with the following type of question for a few Lie groups, but state it for SO(n).
I start with a subgroup ...
2
votes
3
answers
3k
views
Is there any conclusions generalized Singular Value Decomposition into Hilbert Space
Spectrum decomposition can be regarded as the generalizations of the following fact that:
Every Hermitian matrix $A$ can be decomposed into $A=U^{*}\Lambda U$,where $U$ is a unitary matrix
Singular ...
- 1,706
12
votes
4
answers
4k
views
Is any $(n-1)\times (n-1)$ submatrix of an $n \times n$ Vandermonde matrix invertible?
Given an $n \times n$ vandermonde matrix $V$ which is invertible, is any $(n-1) \times (n-1)$ submatrix of $V$ invertible also?
I think the answer is yes, but I don't know how to prove.
- 173
2
votes
3
answers
1k
views
A question on the root systems of simple Lie algebras in the 90 degree case
I've been taking a look at simple Lie algebras for particle physics and I've found myself wondering about the following question. It can be shown that the adjacent roots in a root diagram ...
- 43
5
votes
0
answers
581
views
When is polytope compatible with network flow?
A linear program is the problem of optimizing an linear objective function within some polytope $A$ over $\mathbf R^n$. My question is motivated by the question of when a linear programming problem ...
- 3,475
2
votes
0
answers
200
views
Projecting the unit cube onto subspaces of dimension at least $2$
This is an updated revision of a recent question where I asked:
Given a set $S$ of non-zero vectors in $\mathbb{R}^n,$ and a subspace $L,$ consider $f(S,L)=\max_{s \in S}\frac{\|Ps\|_2}{\|s\|_2}$ ...
- 30.1k