All Questions
6,027 questions
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 ...
- 415
4
votes
1
answer
1k
views
Integer vectors in the kernel of an integer matrix
Let $A$ be a non-zero symmetric $n \times n$-matrix with integer entries and suppose that $\det(A) =0$.
Question: How long is the shortest non-zero integer vector in the kernel of $A$?
Example: If ...
- 25.5k
13
votes
0
answers
713
views
Regular languages of matrices and their generating functions
My question is somewhat related to this question.
Let us fix natural numbers $k$ and $C$. Let $A$ be an automaton whose alphabet consists of $k\times k$ matrices with integer coefficients of ...
- 3,897
4
votes
2
answers
442
views
A mapping from a lattice to itself
Consider $\mathbb{Z}^{n}$ for $n = 2^r$ where $r \geq 1$ . Look at the iterates of the following function $T$ from $\mathbb{Z}^n$ to itself.
$T((a_1, a_2, \ldots, a_n)) = (|a_1 - a_n|, |a_2 - a_1|, |...
- 73
1
vote
2
answers
156
views
How to study the behavior of a particular function on a Vector Space.
Let, $V$ be a vector space over a field $K.$ Let, $T$ be a function from $V$ to $V$ such that
$T(kX) = kT(X)$ for all $k \in K$ and for all $X \in V$ and also
$T(k + X) = T(X)$ for all $k \in K$ ...
- 73
4
votes
1
answer
2k
views
Determinant and symmetric power
Let $V$ be a vector space over some field $k$ and $T \in \mathrm{GL}(V)$. Then, we can view $T\in \mathrm{GL}(\mathrm{Sym}^k(V))$ where $\mathrm{Sym}^k(V)$ denotes the $k^\mathrm{th}$ symmetric power ...
- 1,510
2
votes
3
answers
1k
views
how to get nonzero eigenvalues of a large symmetric matrix with lots of duplicate rows
Is there a nice trick for this? I would like to compute the eigenvalues more efficiently.
- 173
11
votes
4
answers
5k
views
Maximum determinant of $\{0,1\}$-valued $n\times n$-matrices
What's the maximum determinant of $\{0,1\}$ matrices in $M(n,\mathbb{R})$?
If there's no exact formula what are the nearest upper and lower bounds do you know?
- 111
6
votes
1
answer
520
views
Bisymmetric Matrix, solving set of linear equations.
A bisymmetric matrix is a square matrix that is symmetric about both of its main diagonals.
If $A$ is a bisymmetric matrix and I'm interested in solving $Ax=b$.
Are there techniques used to ...
- 3,217
-2
votes
1
answer
470
views
Little conjecture about sums of reciprocals
Given a finite list $x_i$ of $N$ positive reals, it seems that $\sum_{i=1}^N x_i = \sum_{i=1}^N x_i {}^{-1} \Rightarrow \sum_{i=1}^N x_i \geq N$. Can anyone give me a proof?
- 2,513
7
votes
3
answers
2k
views
Is there a field which is the union of finitely many proper subfields?
Is there a field which is the union of finitely many proper subfields?
- 79
4
votes
0
answers
453
views
Convergence of the relaxation method for every parameter in the relevant disk
For large size matrices, the resolution of linear systems $Ax=b$ is often done iteratively. The matrix $A$ is split as $A=M-N$, with $M$ invertible, and one performs
$$x^{k+1}=M^{-1}(Nx^k+b).$$
The ...
- 52.3k
6
votes
0
answers
267
views
Is there a straightforward way to solve unmixed, homogeneous systems of polynomials?
I came across this problem in my research. It might just be an easy algebraic geometry question, but I don't know much algebraic geometry.
Suppose we have a system of $k\leq n$ polynomials in $\...
1
vote
1
answer
383
views
Relaxation Scheme for $Au=f$ error analysis
Hello
I'm trying to answer this question, but am completely stuck.
Argue that in analyzing the error in a stationery linear relaxation scheme applied to $Au=f$, it is sufficient to consider $Au=0$ ...
- 579
2
votes
1
answer
414
views
Descriptive complexity of Hamel bases of R^ω
(base theory = ZFC)
Are any Hamel bases for the vector space $\mathbb{R}^{\omega}$ in the
1. analytical hierarchy?2. projective hierarchy?
In any of the above cases where the answer is not simply ...
user5810
2
votes
1
answer
4k
views
Bidiagonalization and SVD of matrix
I can't find a single solid explanation of how to implement this -- whitepapers too detailed/confusing. Closest I came to an answer was this:
http://www.hep.ucl.ac.uk/~bino/libbpm/doc/pro/html/...
- 123
3
votes
2
answers
4k
views
Matrix products under which the determinant behaves multiplicatively
The determinant behaves multiplicatively with respect to the usual matrix product
$$
\det(AB) = \det(A)\det(B),
$$
and also with respect to the Kronecker (or tensor) product of square matrices
$$
\...
- 403
3
votes
0
answers
1k
views
Determinant of a sum of a diagonal matrix, a dyadic product matrix, and a Hermitian Toeplitz matrix
Hi
From a physics problem, I am trying to evaluate exactly the following kind of determinant:
G = A + M + N.
A is diagonal
M is a product of a column (of 1s) and a row matrix
N is a Hermitian ...
- 31
7
votes
3
answers
3k
views
How many commuting nilpotent matrices are there?
To be precise, fix $n$, fix a field $k$.
What is the maximal dimension of a subspace of the vector space of all $n\times n$ matrices formed by commutative nilpotent matrices? By commutative I mean ...
- 5,052
4
votes
1
answer
3k
views
SVD complexity for structured sparse matrices
Hello,
For an $n \times n$ real matrix, the SVD (Singular Value Decomposition) algorithm is $O(n^3)$.
I have large matrices (say $10,000 \times 10,000$) that only have elements on few diagonals, i.e. ...
- 2,829
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 ...
- 52.3k
1
vote
1
answer
2k
views
Principal Minors of Matrix Product
Suppose $A$ is a positive definite matrix and $B$ is a non-symmetric
matrix with all positive principal minors.
Is their product $AB$ a matrix with all positive principal minors?
I believe the ...
- 1,035
1
vote
1
answer
940
views
maximal number of mutually orthogonal vectors
Let $F$ be a field, $n$ be a positive integer. Denote by $h_{F}(n)$ the maximal dimension of a subspace $X\subset F^n$ such that $(x,y)=0$ for any two (not necessary distinct) vectors $x,y\in F^n$, ...
- 109k
0
votes
1
answer
637
views
Rational solutions of homogeneous equations
Can every solution of a homogeneous linear system be approximated by a solution in rational numbers?
In mathematical terms: Let $$Ax=0$$ be a homogeneous linear system in $n$ determinates for an $m\...
- 10.4k
3
votes
0
answers
328
views
Integer relation detection for Subset Sum or NPP?
Is there a way to encode an instance of Subset Sum or the Number Partition Problem so that a (small) solution to an integer relation yields an answer? If not definitely, then in some probabilistic ...
- 513
4
votes
1
answer
254
views
Embedding into Permutation Representation
Let $\rho$ be irreducible representation of group $G$.
How one can characterize all subgroups $H< G$ such that $\rho$ can be embedded into permutation representation $F^X$, where $X=G/H$.
- 2,179
8
votes
2
answers
679
views
To what extent can algorithms in undergraduate linear algebra be made continuous/polynomial/etc.?
I feel like many of the algorithms that I learned — indeed, that I have taught — in undergraduate linear algebra classes depend sensitively on whether certain numbers are $0$. For example,...
- 54.6k
5
votes
2
answers
3k
views
Closedness of finite-dimensional subspaces
Is the (algebraic) span a finite set of vectors in a Hausdorff topological vector space over a complete field always closed?
I suspect yes, but I can't come up with a proof, and it seems like locally ...
user5810
9
votes
2
answers
1k
views
Other norms for lattice reduction techniques (LLL, PSLQ)?
LLL and other lattice reduction techniques (such as PSLQ) try to find a short basis vector relative to the 2-norm, i.e. for a given basis that has $ \varepsilon $ as its shortest vector, $ \varepsilon ...
- 513
8
votes
1
answer
593
views
Representability of polymatroids over $GF(2)$
A polymatroid is a finite set $X$ and a rank function $d : P(X) \to {\mathbb N}$ such that
1) $d(\varnothing)=0$,
2) $A \subset B$ implies $d(A) \leq d(B)$, and
3) $d(A \cap B) + d(A \cup B) \leq d(...
- 25.5k
2
votes
2
answers
1k
views
Rank of a linear combination of quadratic forms
Suppose we have a set of quadratic forms $Q_i (x_1, \dots, x_n)$ for $1 \leq i \leq k$ in $n$ variables, defined over $\mathbb{R}$. We suppose these are 'collectively nondegenerate' in the sense that ...
- 375
16
votes
3
answers
791
views
Random products of projections: bounds on convergence rate?
The von Neumann-Halperin [vN,H] theorem shows that iterating a fixed product of projection operators converges to the projector onto the intersection subspace of the individual projectors. A good ...
- 181
7
votes
3
answers
744
views
Looking for applications of a nice result in linear algebra
Hello everybody
There is a nice classical result in linear algebra: if $A, B$ are two matrices in $M_n(k),$ where $k$ is a field, and $B$ commutes with every element of $M_n(k)$ which commutes with $...
- 73
2
votes
0
answers
658
views
Alternating bilinear forms over local rings
Suppose k is a field and V a vector space over k. If b is an alternating nondegenerate bilinear form in V, it has a symplectic basis. A symplectic basis is a basis where the basis vectors come in ...
- 7,320
5
votes
5
answers
1k
views
solving series of linear systems with diagonal perturbations
I would like to solve a series of linear systems Ax=b as quickly as quickly as possible. However, the systems are related. Specifically, each matrix A is given by:
cI + E
where E is a fixed sparse, ...
- 135
2
votes
0
answers
241
views
subspace separation and M-matrices
The separation between two square matrices $A$ and $B$, often used as a measure of the sensitivity of invariant subspace problems, is defined as
$$
\operatorname{sep}(A,B)=\min_{X\neq 0}\frac{\left\...
- 20.2k
7
votes
1
answer
372
views
Simultaneously orthogonally transform two SPD matrices to tridiagonal form?
Supposing you have two SPD matrices $A,B\in\mathbb{R}^{n\times n}$ are there any known results on the existence or non-existence of a unitary matrix $Q$ such that $Q^\top A Q=T_A$ and $Q^\top B Q=T_B$ ...
- 71
0
votes
1
answer
551
views
Surface of the cut of an ellipsoid / Marginal density of a multivariate normal over an affine space
So I'm trying to get the marginal density of a multivariate normal over an affine space
if $A$ is a matrix in $\mathbb{R}^p \times \mathbb{R}^n$ for $p < n$ and $B \in \mathbb{R}^n$, $\Sigma$ is a ...
- 1,902
-1
votes
1
answer
1k
views
Sum of two unitary matrix is equal to every matrix? [closed]
Let $R=M_{n}(Z_{2})$, can we write every matrices of $R$ as sum of two matrices of $GL_{n}(Z_{2})$?
- 461
2
votes
2
answers
820
views
eigenvalues of edge regular graphs
In graph theory, an edge regular graph is defined as follows.
Let G = (V,E) be a regular graph with v vertices and degree k.
G is said to be edge regular if there is also integer λ such that:
Every ...
- 461
3
votes
1
answer
572
views
When is a finite matrix a "good" approximate representation of an operator?
I am interested in representing an arbitrary charge density (say, of atoms in a molecule) $\rho(r), \; r\in \mathbb{R}^3$ by a finite linear combination of basis functions
$\rho(r) = \sum_{i=1}^N q_i ...
- 1,890
8
votes
0
answers
1k
views
roots of quadratic forms
This may be a very silly question, but I was wondering what is known about the roots of a quadratic form over variables $x_1,\ldots,x_n,y_1,\ldots,y_m$ in the finite field $\mathbb{F}_p$. I'm not ...
- 131
2
votes
0
answers
299
views
Uniqueness of dimension for topological vector spaces
Let $V$ be a complete Hausdorff locally convex topological vector space over the field $\mathbb{K}$.
Let $B$ be a subset of $V$ satisfying
.
Linearly Independent: For all functions $f$ in $\mathbb{...
user5810
1
vote
3
answers
206
views
Linear space of translatable functions.
What are the functions $f$ so that a set $\{a \cdot f(x+b) : a \in \mathbb{R}, b \in \mathbb{R}\}$ is a finite dimensional linear vector space ?
Is there a complete characterization of such functions?...
- 225
109
votes
19
answers
38k
views
Why were matrix determinants once such a big deal?
I have been told that the study of matrix determinants once comprised the bulk of linear algebra. Today, few textbooks spend more than a few pages to define it and use it to compute a matrix inverse. ...
6
votes
3
answers
2k
views
Conjugate Gradient for a "slightly" singular system.
Suppose I have a symmetric $N \times N$ matrix A which has a one-dimensional Nullspace $N$. A is positive definite on $N^\bot$. In my case $N$ is the space of constant vectors (i.e. generated by ...
- 617
1
vote
2
answers
3k
views
matrices self-adjoint with respect to some inner product
Is it possible to give a nice characterization of matrices $A \in R^{n \times n}$ which are self-adjoint with respect to some inner product?
These matrices include all symmetric matrices (of course) ...
- 415
8
votes
2
answers
4k
views
Estimating the spectral radius of a matrix, noniteratively
Morris Marden's "Geometry of Polynomials" displays a number of formulae that allow one to estimate bounds on the largest root of a polynomial that do not involve actual rootfinding. Having been ...
29
votes
3
answers
3k
views
Perron-Frobenius "inverse eigenvalue problem"
The Perron-Frobenius theorem says that the largest eigenvalue of a positive real matrix (all entries positive) is real. Moreover, that eigenvalue has a positive eigenvector, and it is the only ...
- 2,200
1
vote
1
answer
201
views
How can I characterize the type of solution vector that comes out of a matrix?
Ax = b. I need a way to analyze a square matrix A to see if its solution vector x will ...
- 133