Questions about the properties of vector spaces and linear transformations, including linear systems in general.

learn more… | top users | synonyms

4
votes
2answers
205 views

Why are the vectors with this special structure linearly independent with high probability?

Given $a_i\in\mathbb{R}^m$ for $i=1,\ldots,2m$ with independent and identically random entries of some continuous distribution. Every choice of $m$ vectors from $\{a_1\ldots,a_{2m}\}$ is linearly ...
11
votes
1answer
431 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 ...
5
votes
2answers
201 views

Induced matrix norm less than one for matrices with spectral radius less than one

Let $A$ be a square matrix with elements in $\mathbb{R}$ or $\mathbb{C}$, $\rho\left(A\right)$ stands for the spectral radius of $A$, i.e., the maximum absolute eigenvalue of $A$; $A^{*}$ is the ...
0
votes
0answers
33 views

If $A$ is doubly stochastic and reducible. Why is $A$ permutation similar to a matrix of the form $A_1 ⊕ A_2$

If $A \in M_n$ is doubly stochastic and reducible. Why is $A$ permutation similar to a matrix of the form $A_1 ⊕ A_2$, in which both $A_1$ and $A_2$ are doubly stochastic?
1
vote
0answers
75 views

Let $M = \frac{1}{2}(A + {A^T})$ be real symmetric nonnegative matrix. Why does $\rho (A) \le {\lambda _{\max }}(M)$?

Let $A \in M_n$ be nonnegative, and consider the real symmetric nonnegative matrix $M = \frac{1}{2}(A + {A^T})$. Why does $\rho (A) \le {\lambda _{\max }}(M)$?
1
vote
1answer
79 views

Multiplicatively closed subsets of $\mathbb{C}^{n \times n}$

While dealing with another problem I saw that I need to classify subspaces $V$ of $\mathbb{C}^{n \times n}$ that are multiplicatively closed. So to get an idea of the nature of the subspaces I ...
0
votes
1answer
115 views

Standard rational functions from matrices

In linear algebra we get introduced to standard polynomials that are associated to matrices such as characteristic polynomials and determinants. What are some of the standard rational functions that ...
1
vote
1answer
75 views

$0/1$ programming multiple quadratic constraints

If we have an $n$-variable rank $n$-linear system it is clear we can find whether there exists a $0/1$ solution in polynomial time. If we have an $n$-variable degree $2$ system how many constraints ...
0
votes
2answers
406 views

Solving a system of equations using Gröbner basis

In Sage (or any other package) when using Gröbner basis to solve a system of equations (some of which are non-linear equations) does computing the Gröbner basis for the ideal ID generated by the ...
1
vote
0answers
17 views

How to find a subset of a matrix that has minimum condition number? [duplicate]

Suppose matrix $A$ is consist of M column vectors, how can we find a subset $B$, consisting of N column of $A$ (N<M), that has minimum condition number (the ratio of maximum singular value by minimum ...
0
votes
0answers
53 views

An extremal combinatorics problem

What is the minimum rank $r$ of an $n\times n$ square positive integer matrix such that sum of entries of every $\sqrt r\times\sqrt r$ submatrix is distinct and such that difference between minimum ...
1
vote
0answers
53 views

How to associate the following two kinds of real polynomials?

Suppose the following real polynomial of $n$ variables $$f(X_1,X_2,\cdots,X_n)=\sum_{I=(i_1,i_2,\cdots,i_n)}a_IX_1^{i_1}X_2^{i_2}\cdots X_n^{i_n}$$ is easy or familiar to us, but I need to deal with ...
1
vote
0answers
72 views

A question on Perron–Frobenius theorem [closed]

Let $A \in M_n$ is nonnegative(all $a_{ij}\ge0$). Suppose $A$ has a nonnegative eigenvector(all entries$\ge0$ ) with $r ≥ 1$ positive entries and $n − r$ zero entries. Why is there a permutation ...
4
votes
1answer
130 views

subset of hermitian matrices given by eigenvalues form a submanifold

Let $\mathcal{O}_\lambda$ be the set of hermitian $n+1 \times n+1$ matrices with Eigenvalues $\lambda = (\lambda_1, \dots, \lambda_{n+1})$. and $\mathcal{O}^\mu$ the set of hermitian $n \times n$ ...
6
votes
1answer
192 views

Bounds for maximum determinant of circulant matrices

The Hadamard circulant conjecture states that there do not exist circulant Hadamard matrices with more than $4$ columns. An $n$ by $n$ Hadamard matrix where the entries are chosen from $\{-1,1\}$ ...
2
votes
1answer
96 views

Heuristics for counting degrees of freedom

I have recently learned about the representation theorem for isotropic, linear operators, which says the following: Defintion: Let $M_n$ be the vector space of $n \times n$ real matrices. We say a ...
6
votes
1answer
453 views

Why is $(A^\perp)^\perp = A$?

On page 52 of this paper, Iwasawa considered the bilinear symmetric non-degenerate pairing $\Phi_n \times \Phi_n \rightarrow \mathbb{Q}_p/\mathbb{Z}_p$ defined by $$\langle \alpha, \beta \rangle_n := ...
1
vote
1answer
205 views

Solving Non-Linear Equations over a Finite Field of a Large Prime Order

I want to know is there is an efficient way to figure out whether or not a ( underdetermined) system of non-linear equations have a solution over a finite field of large prime order. The equations ...
11
votes
4answers
864 views

Probability two products are equal

I am interested in the following simple looking problem on which I am stuck. Let $M$ be a fixed $m$ by $n$ matrix with $\pm1$ elements. Let $x$ and $y$ be two independently sampled random ...
10
votes
2answers
268 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 ...
3
votes
1answer
198 views

Why is dual lattice a lattice, in the context of complex tori

I have a simple linear algebra question regarding the definition of dual of a lattice; it was asked by someone else here three months ago on mathstackexchange but got no answer and few views, so ...
0
votes
0answers
244 views

When does this matrix have full rank?

Suppose $\mathbf{B}\in\left[0,1\right]^{T\times M}$ is a binary matrix, $\mathbf{B}_{i}$ is a column of $\mathbf{B}$, and $\mathbf{X}\in\mathbb{R}^{N\times T}$ is a matrix where the columns are ...
2
votes
0answers
121 views

Which functions preserve the connectivity of graphs/components?

I am somewhat stuck working on an issue and would really love some guidance. I will state the problem, my current state and what led to it in case the solution lies beyond where I was looking The ...
0
votes
2answers
81 views

Simultaneous special orthogonal similarity problem

Given matrices $A,B,C,D\in\Bbb K^{n\times n}$ where $\Bbb K$ is a ring is there an efficient technique to compute set $O$ with $OO'=I$ where $'$ is transpose and $\mathsf{Det}(O)=\pm1$ such that ...
0
votes
0answers
66 views

Simplifying product of matrix exponential?

Is there a known generalization for n-term matrix exponential multiplication? I am aware that the Baker–Campbell–Hausdorff formula could be used, e.g.: ...
0
votes
0answers
97 views

A linear combination problem

Given $0/1$ $n\times n$ matrix $M$. Suppose we have $2$ vectors $\lambda,\mu\in\Bbb R^{1\times n}$ such that both $$\lambda M\in\{0,1\}^{1\times n}$$ $$M\mu'\in\{0,1\}^{n\times 1}$$ holds with $'$ ...
5
votes
1answer
217 views

Minimize Frobenius norm

My question is the following: Suppose $M$ is an $n \times n$ symmetric real matrix. I want to find an $n \times n$ symmetric real matrix X such that $|| X -M||_F$ is minimized with the constraint ...
4
votes
0answers
204 views

A combinatorial problem

What is the largest $m\times m$ $0/1$ matrix of real rank $n$ with every square submatrix sized at least ${n^{\gamma}}\times{n^{\gamma}}$ distinct for some fixed $\gamma>0$? Upper Bounds: Number ...
1
vote
1answer
62 views

Reduced echelon form of sparce matrices and constructing hash function

Let $G$ be a $d$-regular graph, and $A$ be the incidence matrix of $G$. Also suppose $B$ is a reduced echelon form of $A$ such that computations are in $\mathbb F_2$. Given matrix $B$, can we find ...
2
votes
1answer
152 views

Division and multiplication that preserve Euclidean norms

I am looking for ways to define $$\frac{1}{x}\in \mathbb{R}^n\quad \quad and\quad \quad x\cdot y\in \mathbb{R}^n ,$$ where $x,y\in \mathbb{R}^n$ such that ...
5
votes
1answer
162 views

Eigenvalues of $X$ in the metric of $Y$

What does this statement describe? $X$ and $Y$ are matrices. The eigenvalues of $X$ in the metric of $Y$. I've not seen this language used before in this fashion and I don't really know what ...
0
votes
1answer
49 views

Is spectral properties a general term for condition number?

I am reading an article about solving large sparse linear systems, in this paper it’s said that most of the iterative methods to solve $Ax = b$ are very much influenced by the spectral properties of ...
0
votes
0answers
105 views

Comparison of Parameter estimation using maximum likelihood and Maximum entropy

I am not sure if the question is appropriate but I want to try my luck. One can estimate a parameter using maximum likelihood and we know it is optimal. On the other hand there are methods which uses ...
2
votes
1answer
87 views

Eigenvalues of product of symplectic matrices

I have 2 symplectic matrices $X_{1},X_{2} \in \mathbb{R}^{2n\times2n}$. The matrix $X=X_{1} \cdot X_{2}$ is also symplectic. Question: Are there any theorems which allow me to express eigenvalues of ...
1
vote
2answers
63 views

Sensitivity analysis in minimum norm problems under a linear constraint

Suppose $\Delta$ is some nice topological space, say compact, and Hausdorff. Let $A:\Delta \rightarrow \mathbb{R}^{m\times n}$ be a continuous $m\times n$ matrix valued map. Let $b\in \mathbb{R}^{m}$ ...
0
votes
0answers
40 views

Can the maximal eigenvalue of Toeplitz hermitian be bound by one entry?

Let $T$ be $N \times N$ toeplitz hermitian matrix. Assuming we control the entry $T_{N,1}$ with the other entries fixed. Can we determine the maximal eigenvalue of $T$, or at least bound it?
11
votes
1answer
213 views

Is this generalization of eigenvalue and eigenvector studied?

While thinking about what it means for observables to be simultaneously measurable in quantum mechanics I came up with the following concepts, which I will call "linearly indexed" versions of standard ...
7
votes
1answer
103 views

$\text{GL}(n + k, \mathbb{R})$ is a principal $H$ bundle over the Grassmann manifold $G_n(\mathbb{R}^{n+k})$?

Let $H$ be the subgroup of $\text{GL}(n + k, \mathbb{R})$ consisting of matrices whose lower $n \times k$ block is empty; i.e. consisting of matrices of the form$$\begin{pmatrix} A & * \\ 0 & ...
5
votes
1answer
162 views

Continuity of solutions to $Av=b$

Let $X$ be a compact Hausdorff topological space, and $C(X)$ denote the ring of complex-valued, continuous functions on $X$. Let $A$ be a matrix with entries from $C(X)$ of size $m\times n$ and $b\in ...
8
votes
1answer
251 views

Efficiently compute the trace of a sparse matrix times the inverse of a sparse matrix?

How can I efficiently compute $\mathrm{trace}(A(B^{-1}))$ where $A$ and $B$ are both sparse symmetric PSD $n \times n$ matrices, both with $O(n)$ non-zero entries? If it helps, the pattern of ...
9
votes
1answer
465 views

What is the spin connection in 9 dimensions as opposed to 5 dimensions?

From Spin Connection in 5 dimensions I can define a massless fermion's covariant derivative on a curved manifold as $$ \nabla_\mu \psi = (\partial_\mu - {i \over 4} \omega_\mu^{ab} \sigma_{ab}) \psi ...
4
votes
2answers
268 views

Is it always possible to “separate” the eigenvalues of an integer matrix?

Call a square matrix Galois-irreducible if all its eigenvalues are Galois conjugates of each other. Let $M$ be an integer $n\times n$ matrix which is not Galois-irreducible. Is it always ...
1
vote
1answer
200 views

Testing $0$ for a determinant like function [closed]

Given $A\in\Bbb Z^{n\times n}$ we have $$Det(A)=\sum_{\sigma\in S_n}(-1)^{sgn(\sigma)}\prod_{j=1}^nA_{j\sigma(j)}$$ We can test when this is $0$ by looking at the rank in polynomial time. Can either ...
4
votes
3answers
150 views

Fast Upper Triangular Matrix Exponentiation

Let $Q_n$ be a $n\times n$ matrix with $Q_n=\begin{pmatrix} -\lambda_1-\mu_1 & \lambda_1 & 0 & \cdots\\ 0 & -\lambda_2-\mu_2 & \lambda_2 & \cdots\\ \vdots & \vdots & ...
1
vote
0answers
48 views

References for a minor variant of the Rayleigh quotient

I believe this variant of the Rayleigh quotient inequality must be well known but I could not find references for it online. It's proof is straightforward. Let $\mathbf{A}\in\mathbb{R}^{n\times n}$ ...
0
votes
1answer
51 views

Approximate $\mathbf{G}=(a\mathbf{H}+\mathbf{M})^+$ by Taylor expansion [closed]

Suppose we have a complex matrix $\mathbf{M}$. Let $\mathbf{M}^+=(\mathbf{M}^*\mathbf{M})^{-1}\mathbf{M}^*$ be the pseudo-inverse of $\mathbf{M}$, where $^*$ denotes the conjugate transpose. Let ...
10
votes
1answer
193 views

On Sampling rank $r$ matrices

Sample $n^2$ integers $a_{11},\dots,a_{nn}$ in $\{-d,\dots,-1,0,1\dots,d\}$ uniformly. What is the probability that the resulting matrix $[a_{ij}]$ has rank $r$? Is there a nice parametrization of ...
6
votes
1answer
279 views

Encyclopedia of properties of nonnegative matrices

I'd like to buy a book that contains more or less all known properties of elementwise nonnegative nonnegative matrices, i.e. matrices $A$ such that $A_{i,j}\geq 0$ for all $i,j$. Chapter 8 in ...
2
votes
2answers
104 views

Orthogonal Procrustes problem with Absolute Values

Given a non-negative matrix $T$, how to find a orthogonal matrix $O$ minimising $$ \left\lVert \, |O| - T \right\lVert_F,$$ where $\lVert \cdot \lVert_F$ denotes the Frobenius norm, and $| \cdot |$ ...
7
votes
1answer
152 views

approximate stationary distributions of a doubly stochastic matrix and its supports

Given a doubly stochastic matrix $M$ and a distribution $v$,let $M=\sum_{\sigma\in S_n}p_{\sigma}M_{\sigma}$ be any Birkhoff decomposition of $M$, where $M_{\sigma}$ is the permutation matrix induced ...