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

learn more… | top users | synonyms

11
votes
1answer
371 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
113 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
64 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
78 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
113 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
72 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
338 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
49 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
50 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
68 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
119 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
184 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
74 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
445 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
175 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
853 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
248 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
185 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
234 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
118 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
65 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
54 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.: ...
1
vote
0answers
95 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
88 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 ...
5
votes
0answers
199 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 ...
4
votes
0answers
95 views

A $0/1$ matrix problem

What is the largest $m\times m$ $0/1$ square matrix of rank $2n$ over $\Bbb R$ we can have such that every submatrix sized at least $n\times n$ has rank at least $\sqrt{n}$?
1
vote
1answer
61 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
143 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
141 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
44 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
92 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
82 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
60 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
38 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?
9
votes
0answers
155 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 ...
0
votes
0answers
44 views

references for semi-linear algebra over fields

What is a good reference for semi-linear algebra? In particular semi-linear transformations and their matrix representations.
7
votes
1answer
100 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
160 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 ...
6
votes
1answer
109 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
451 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
254 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
199 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
119 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
43 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
49 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
191 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
270 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 ...
1
vote
2answers
74 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 |$ ...