All Questions
1,923 questions with no upvoted or accepted answers
6
votes
0
answers
111
views
Factorization to sparse matrices
$\newcommand{\lrank}{\operatorname{lrank}}$
$\newcommand{\rank}{\operatorname{rank}}$
Given a matrix $A$, we can define its Hamming weight, $w(A)$, as the number of non-zero elements in it.
Now, given ...
- 3,319
6
votes
0
answers
188
views
Expressing an invertible sparse matrix as a product of few elementary matrices
Let $M$ be an $n \times n$ matrix with integer entries. Suppose that $M$ is invertible (over the integers) and that $M$ has at most $An$ nonzero entries, each of which is less than $B$ in absolute ...
- 18.7k
6
votes
0
answers
279
views
Estimating $E[\operatorname{Tr}(ABABBA..)]$ for random shuffling of $A,B$?
How can I estimate the following value where $A,B$ are $d\times d$ matrices and expectation is taken over all random permutations of the product?
$$E_\text{shuffle}[\operatorname{Tr}\underbrace{AA\...
- 2,252
6
votes
0
answers
138
views
Minimizing $\det(D)$ for all diagonal matrices $D$ that satisfy $D+B \succeq 0$
Let $A$ be an $n \times n$ real matrix and let $B$ be the block bipartite matrix
$$B = \begin{bmatrix} 0&A \\
A^{T}&0 \end{bmatrix}$$
I came across the following optimization problem, which ...
- 401
6
votes
0
answers
340
views
Asymptotically nilpotent Lie sets of matrices
A matrix $A\in\textbf{Mat}_n(\mathbb{R})$ is called asymptotically nilpotent if for each vector $v$, ${\lim}_{k\to\infty}A^k(v) = 0$.
Question 1. Assume that $\mathcal{A}$ is the subset of $\textbf{...
- 291
6
votes
0
answers
392
views
Divisibility properties of minors of matrices
Let $A$ be an $m\times n$ matrix with integer entries. Let $d_i(A)$ be the greatest common divisor of all $i\times i$ minors of $A$, and define $d_0(A)=1$. Whenever $i\leq j$, one has that $d_i(A)$ ...
- 191
6
votes
0
answers
353
views
Atiyah–Singer Index theorem for the pedestrian / layperson
So I came across the so-called Atiyah–Singer Index Theorem (ASIT) and claims of it being an extremely powerful and versatile tool.
Question. What is a truly simple application of the ASIT to obtain a ...
- 6,853
6
votes
0
answers
173
views
Orlik-Solomon algebra and hyperplane complements in positive characteristic
Let $k$ be an algebraically closed field of characteristic $p\geq 0$, $\underline H:=\{H_1,\dots, H_m\}$ a set of hyperplanes in $\mathbb A_k^n$ and $X:=\mathbb A^n-(\bigcup H_i)$.
Given a ring $R$ ...
- 728
6
votes
0
answers
113
views
$S_n$-invariant polynomials on the dual of reflection representation
Let $W=S_n$ (the symmetric group) acting on $V=k^n$ via permutation of the indices, where $k$ is an algebraically closed field. Closely related to this are the reflection (sub-)representation $V_0=\{ (...
- 1,336
6
votes
0
answers
172
views
Eigenvalues of symmetric matrices associated to posets
For a finite connected poset $P$ define the Cartan matrix $C$ as the matrix with entries $c_{i,j}=1$ if $i \leq j$ and $c_{i,j}=0$ else, where $i,j\in P$.
Define the Frobenius-Cartan matrix of $P$ as $...
- 26.5k
6
votes
0
answers
107
views
Eigenvalues of splitting scheme
In numerical analysis it is common to approximate a solution to a PDE
$$u'(t) = (A+B) u(t), \quad u(0)=u_0$$
which is just given by $e^{t(A+B)}u_0$ by the splitting $e^{tB/2} e^{tA} e^{tB/2}u_0.$ Here,...
- 536
6
votes
0
answers
588
views
Expressing a polynomial as the determinant of a matrix of linear forms
I have heard that it's a well known result (in theoretical computer science?) that if we have a polynomial $p(t_1,\dots,t_n)$ over $\mathbb Q$, we can find matrices $M_0,\dots,M_n/\mathbb Q$ such that ...
- 7,746
6
votes
0
answers
335
views
Galois groups associated to matrices
When $A\in M_n(\mathbb{Q})$, we consider the pencil $A-xA^T$. Then $p_A(x)=\det(A-xA^T)$ is a self-reciprocal polynomial. $p_A$ can only be irreducible if $n=2p$ is even.
Question: For every $p$, does ...
- 3,741
6
votes
0
answers
652
views
Counting the number of linearly independent primitive elements of a field extension
Let $L/K$ be a field extension with extension degree $n>1$. We say $L/K$ is simple if $L=K(a)$ for some a in $L$. In this case, $a$ is called a primitive element. My question is now about the ...
- 429
6
votes
0
answers
317
views
Eigenvectors of a symmetric sum of tensor products
Let $A$ and $B$ be two (finite-dimensional) Hermitian matrices and $n$ be a positive integer. We define the matrix
$$
L_i = A\otimes \dots\otimes A\otimes B\otimes A\otimes \dots\otimes A~,
$$
where ...
- 63
6
votes
0
answers
192
views
Bar notation in Bourbaki’s *Lie groups*, Chap. IX
I am looking at Chapter IX (Compact Real Lie Groups), §4, Exercise 8 (translation). Given a complex subspace $\mathfrak p$ in the complexification $\mathfrak g_{\mathbf C}$ of some $\mathfrak g$, they ...
- 31.5k
6
votes
0
answers
217
views
Is this function embeddable in Euclidean space?
Let $X = \{v_1,\ldots,v_n\}$ be a set of vectors non-zero vectors $v_i \ge 0$ and such that the vectors are pairwise linear independent. Define a function on this set $X$:
$$d(v,w) = 1-\frac{2 \...
user6671
6
votes
0
answers
141
views
Algorithm to check a conjectural value for the rank of a large matrix
Feel free to suggest a different title, I'm not sure how to phrase this. I'm in the following somewhat specific situation:
I'm checking a conjecture which at the end of the day boils down to the ...
- 8,524
6
votes
0
answers
96
views
Finding the maximal component of a vector in sublinear time
Given a vector $u \in \Bbb R^n$, finding the value of the largest component of $u$ needs linear time in $n$. However, what if we additionally know that $u$ lies in some linear subspace $U \subset \Bbb ...
- 13.6k
6
votes
0
answers
211
views
Lambek calculus, linear logic, and linear algebra
In his 1958 paper, The Mathematics of Sentence Structure, Joachim Lambek introduced the Lambek calculus. In modern terms, it could be understood as a syntax for biclosed
monoidal categories, and he ...
- 9,201
6
votes
0
answers
391
views
Is there an easy way to compute the maximum isotropic subspace over finite fields?
Given a quadratic form (or a symmetric $n \times n$ matrix $A$), an isotropic subspace is a subspace $U$ such that $$U^t A U=0,$$
If I am not mistaken, when the matrix is over reals, the maximum ...
- 571
6
votes
0
answers
126
views
mean distance between subspaces
Consider the Haar measure $\mu$ on the Grassmannian $G(n, k)$ of $k$-dimensional subspaces in $\mathbb{R}^n.$ Now, pick pairs of subspaces uniformly at random with respect to $\mu,$ and compute their ...
- 96.4k
6
votes
0
answers
413
views
Find a condition such that the spectral radius for a special matrix is smaller than 1 (or a matrix norm smaller than 1)
We need a help to find a reasonable condition such that the spectral radius for a special matrix $\mathbf{J} \otimes\hat{\mathbf{G}}\hat{\mathbf{W}} + \mathbf{I}\otimes\mathbf{\hat{H}}$ is smaller ...
- 272
6
votes
0
answers
177
views
Determinant arising in a problem from probability
Consider the determinant:
$$\Delta:=
\left|\begin{array}{cccc}
A_{j_1} & A_{k_1} & A_{j_1}A_{k_1} & 1 \\
A_{j_2} & A_{k_2} & A_{j_2}A_{k_2} & 1 \\
A_{j_3 } & A_{k_3 } &...
- 783
6
votes
0
answers
185
views
Is this "stretched eigenvector" studied? (If so, what are its properties?)
An eigenvector is defined by
$$
\lambda \mathbf{v} = A\mathbf{v}.\tag{1}
$$
But suppose I change this to
$$
\lambda \mathbf{v} = A\mathbf{v}^\alpha,\tag{2}
$$
for real $\alpha\ne 1$, where $\mathbf{v}^...
- 1,344
6
votes
0
answers
224
views
Specifying cokernels of all powers of $p$-adic matrix
Given a matrix $A \in M_d(\mathbb{Z}_p)$ (with nonzero determinant), viewed as a map $\mathbb{Z}_p^d \to \mathbb{Z}_p^d$, I am interested in the sequence of abelian $p$-groups $\{coker(A^n)\}_{n \geq ...
- 568
6
votes
0
answers
99
views
What is this matrix decomposition called and does it exist always? - II
Given a rank $2r$ matrix $M\in\Bbb Q_{\geq0}^{n\times n}$ can we find two matrices $M_+\in\Bbb Q_{\geq0}^{n\times n}$ and $M_-\in\Bbb Q_{\geq0}^{n\times n}$ each of rank at most $r$ such that $M=M_+-...
- 13.9k
6
votes
0
answers
218
views
Reconstruct orthogonal from an orthostochastic matrix
Given an $n \times n$ orthostochastic matrix $\mathbf{A}$, i.e., there exists an orthogonal matrix $\mathbf{O}$ with $A_{ij} = O_{ij}^2$ for all $1\leq i,j \leq n$. What is the fastest way to find $\...
- 909
6
votes
0
answers
444
views
Solve this nonlinear matrix equation?
For $M$ and $N$ two invertible square matrices of the same size $n$, consider the equation
$$
\forall i,j, \quad M_{ij}(M^{-1})_{ji} = N_{ij}(N^{-1})_{ji}\ .
$$
Assuming we know $M$, we want to find ...
- 378
6
votes
0
answers
297
views
formalization of coordinate-free linear algebra in a proof assistant
I am aware of projects that formalize linear algebra in existing proof assistants (i.e. Coq), but it seems like most of them are based on matrices. I was wondering if it's done in a coordinate-free ...
- 161
6
votes
0
answers
106
views
A conjectured trace inequality for some products of powers of matrices II
Let $B, R\in M_{n}(\mathbb{C})$ hermitian and $B$ positive semidefinite.
Let $s \in \mathbb{R}$ and $s \ge 0$ .
Does then hold $Tr[B^s (I + B R^2 B)^{-1}] \le Tr[B^s (I + R B^2 R)^{-1}]$ ?
See also ...
- 2,753
6
votes
0
answers
291
views
Upper bound for $\|\textbf{D}^{-1}\|$, where $\textbf{D}$ is a matrix with specific sparse pattern
Consider the block matrix given by
$$\textbf{D} = \left[
\begin{array}{ccc}
\left[
\begin{array}{ccc}
D & \ldots & D\\
\vdots & \ddots & \vdots\\
D &...
- 143
6
votes
0
answers
133
views
Is the map taking a matrix to its semisimple part algebraic (or at least holomorphic)?
Let $\text{Mat}_n(\mathbb{C})$ be the set of $n \times n$ complex matrices. Let $\sigma\colon \text{Mat}_n(\mathbb{C}) \rightarrow \text{Mat}_n(\mathbb{C})$ be the map that takes a matrix to its ...
- 61
6
votes
0
answers
179
views
Growth in a vector space
I am interested in "growth" in finite vector spaces. I have been wondering about the veracity of the following statement:
Statement: For every $\varepsilon>0$ there exists $b\in\mathbb{Z}^+$ ...
- 11.2k
6
votes
0
answers
375
views
Monomial base change and the Vandermonde
Denote the falling factorials by $(x)_k=x(x-1)\cdots(x-k+1)$.
The Vandermonde determinant is given by $\det\left[x_i^{j-1}\right]_1^n=\prod_{i<j}(x_j-x_i)$.
It is well-known that in as much as ...
- 43.2k
6
votes
0
answers
450
views
Can this nonlinear vector equation be solved analytically?
I have the following vector equation:
$$
{\bf Ax} + {\bf b} + {\bf Cx}^{ \circ - 1} = {\bf 0}_n
$$
Where ${\bf x}$ is a vector of unknown variables. ${\bf b},{\bf x}, {\bf x}^{\circ - 1}, {\bf 0}_n ...
- 235
6
votes
0
answers
343
views
Are all stabilizer groups of the co-adjoint action smooth?
Let $k$ be a (non-archimedean) local field of positive characteristic $p$ and $\mathfrak{n}$ be any finite-dimensional nilpotent Lie algebra over $k$ with nilpotence length $l<p$. It is well-known ...
- 1,702
6
votes
0
answers
467
views
Torsionfree crystalline cohomology implies torsionfree etale cohomology?
Let $X$ be a smooth projective variety over an algebraically closed field $k$ of characteristic $p>0$. Let $W=W(k)$ be the ring of Witt vectors of $k$.
Assume that the crystalline cohomology $H^2_{...
- 91
6
votes
0
answers
215
views
Matrix semigroups in which a weighted average of eigenvalues is multiplicative
A problem in fractal geometry requires me to consider matrix semigroups with the following curious property. For a $d \times d$ real matrix $A$ let $\lambda_1(A) \geq \lambda_2(A) \geq \cdots \geq \...
- 6,206
6
votes
0
answers
588
views
Lower bound on the sum of singular values for a sum of Hermitian matrices
Denote the eigenvalues of an $n\times n$ matrix $\mathbf{X}$ by $\lambda_i(\mathbf{X})$ and its singular values by $\sigma_i(\mathbf{X})$, $i=1,\ldots,n$. When $\mathbf{X}$ is Hermitian, we know that $...
- 917
6
votes
0
answers
721
views
Sum of the entries of the inverse covariance matrix
Let $T \in\left(0,1\right)$, $n\in\mathbb{N}$ and $e_n = [1,\ldots,1]\in\mathbb{R}^n$. Consider the covariance matrix $\mathfrak{A}_n = \left[sinc\left(\frac{T\left(r-s\right)}{n}\right)\right]^n_{r,s=...
- 159
6
votes
0
answers
489
views
Symmetric matrices with $\rho(A)\gg\|A\|_\infty$
For a symmetric real matrix $A$, denote by $\rho(A)$ the spectral radius of $A$, and by $\sigma(A)$ the largest absolute row sum of $A$; that is, $\sigma(A)=\max_i \sum_j |a_{ij}|$, where $a_{ij}$ are ...
- 23k
6
votes
0
answers
375
views
Kasteleyn, Gessel-Viennot and eigenvalues
The Kasteleyn matrix (for counting perfect matchings) and the Lindström-Gessel-Viennot matrix (for counting families of nonintersecting lattice paths) are tightly related, as observed many times by ...
- 1,343
6
votes
0
answers
319
views
Variant of orthogonal Procrustes problem
The orthogonal Procrustes problem seeks a matrix $M$ that minimizes $||AM-B||_F$ subject to $M^TM=I$, where $M$ is $d\times d$ and both $A$ and $B$ are $n\times d$. Geometrically, $M$ rotates a set of ...
- 61
6
votes
0
answers
514
views
concentration for eigenvectors
I am interested in bounding from above the ratio between the maximum and minimum entries of a Perron vector. The only results that I found in the literature are from the classic masters (Ostrowski and ...
- 6,962
6
votes
0
answers
465
views
Spaces of matrices with same eigenvalue/Great circles in O(n)-orbits
Let $Sym^2(V)$ be the set of symmetric matrices of a real $n$-dimensional vector space $V$. Given an element $\underline{\lambda}=[\lambda_1,\ldots \lambda_n]\in \mathbb{RP}^n$, where $\lambda_1\leq\...
- 1,452
6
votes
0
answers
436
views
Do there exist weak Lefschetz-type statements that were proved for varieties over complex numbers, but were not proved in finite characteristic?
As far as I understood the situation (reading section 3.5B of Lazarsfeld's "Positivity in algebraic geometry" and also some of the references), some of weak Lefschetz-type statements known rely on '...
- 16.9k
6
votes
0
answers
1k
views
Generalized Courant-Fischer theorem
Consider some quaternionic matrix $A$. A right eigvenvalue of $A$ is a quaternion $q$ such that $Ax=xq$ for some $x\in \mathbb{H}^n$. Similarly, a left eigenvalue of $A$ is quaternion $q$ such that $...
- 475
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 $\...
6
votes
0
answers
456
views
On periods of algebraic integers modulo rational primes
I run, somewhat indirectly, into the following problem and I have no hints where to look in the literature in search for answers or clues.
Let $K$ be a number field, which we may assume Galois if it ...
- 797