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

learn more… | top users | synonyms

1
vote
0answers
26 views

Heuristic for choosing n-vectors from n-sets

my given problem is: choose n-vectors from n-sets (one vector from each set) so that the biggest element in the sum of the chosen vectors is minimal. Unfortunately the problem is NP-hard. So I'm ...
2
votes
1answer
81 views

Triangular Smoothing Formula Optimization

I'm using a 5-point Triangle Moving Average: $$S_j = (Y_{j-2} + 2Y_{j-1} + 3Y_j + 2Y_{j+1} + Y_{j+2}) / 9$$ The problem is that I often need to smooth my data more than once, and when I do this too ...
0
votes
0answers
42 views

Spanning Hadamard product powers (Schur products) in Euclidean space

This is a question I asked last year over at stackexchange. Got no answer, it might be sufficiently non-trivial to justify bringing it into here. Fix two $k$-vectors $\mathbf u$ and $\mathbf v$, and ...
3
votes
4answers
344 views

Reference for an algebraic group preserving a cubic form

Let $R=k[u,v,w]$ and $p\in R$ be a cubic form. Let $G$ be the group of graded automorphisms of $R$ which preserve $p$, i.e., $G$ is the subgroup of $GL_3(k)$ consisting of elements $g$ such that $g(p) ...
4
votes
0answers
91 views

A question on hyperplanes in partial linear spaces and hypergraphs

A partial linear space (or a linear hypergraph) is a point line geometry $(P,L,I)$ where for every pair of points there is at most one line incident with both of them. A hyperplane in a partial linear ...
0
votes
1answer
72 views

Decompositions of sparse symmetric matrices and methods for solving large linear equations

I am writing code for solving linear equations of the form $$A_{n\times n}\cdot x=1_n$$ where $n$ is on the order of $10^6$ and $A$ is a symmetric matrix with approx $10^3$ nonzero entries in each ...
6
votes
2answers
257 views

Does small Perron-Frobenius eigenvalue imply small entries for integral matrices?

Suppose that $M$ is an $n \times n$ matrix where each entry is a positive integer. Then $M$ is Perron-Frobenius and so has unique largest real eigenvalue $\lambda_{\textrm{PF}}$. Does an upper ...
6
votes
1answer
194 views

Solving for a set of points from projections

Consider a set of $N$ points in $n$-dimensional space, i.e. \begin{align*} S = \{x_1, \dots, x_N\} \subset \mathbb R^n. \end{align*} Let $v \in \mathbb R^n$ and consider the image set (not counting ...
1
vote
1answer
80 views

Bound on the 2-norm of a “special” matrix

Let $S\in\mathbb{R}^{n\times n}$ be such that $\|S\|_2\leq 1$, $P\in\mathbb{R}^{n\times m}$, $m<n$, with orthogonal columns ($P^TP=I$) so that $PP^T$ and $I-PP^T$ are orthogonal projectors, and ...
1
vote
2answers
254 views

when will the surfficient large power of a rational matrix be a integer matrix?

$A$ is a $n\times n$ matrix whose elements are all non-negative rational numbers and $Det(A)$ is a non-zero integer.Under what condition the following is true?(0) There exist a positive integer $M$ ...
2
votes
1answer
88 views

General method for under and over determined systems?

Suppose I have a system: $$ Ax = b $$ where $A$ is a $m$ by $n$ matrix which is less than full rank (neither full column nor row rank). In my particular case $m<n$. I'd like a combination of a ...
2
votes
0answers
317 views

The twisted kiss of the curvaceous cubic and the staid tetrahedron (references)

(Migrated from MSE) While investigating some operators, I came across some relations between the twisted cubic curve and the tetrahedron that link together some notions in differential geometry, ...
0
votes
0answers
50 views

Linear Bounds on estimation error

Consider a markov chain on discrete state space $\mathbb{S} = \left\{1,2,..,S \right\}$, with transition probability matrix defined as $A = [a_{ij}]_{S \times S}$ where $a_{ij} = ...
-2
votes
1answer
90 views

Is dual cone unique? [closed]

Suppose we have the following relationship, note that $A,B,C$ are closed convex matrix cones, $A^\ast=C,$ $B^\ast=C,$ can we state that $A=B$? Is the dual cone of a cone is unique? the definition ...
2
votes
2answers
344 views

Central idempotents from characters in Frobenius algebras (generalizing Lusztig arXiv:math/0208154v1 §19)

$\newcommand{\refone}{\textbf{(1)}}$ $\newcommand{\Hom}{\operatorname{Hom}}$ $\newcommand{\tr}{\operatorname{Tr}}$ $\newcommand{\kk}{\mathbf{k}}$ Let $\kk$ be a field. Let $A$ be a $\kk$-algebra which ...
1
vote
0answers
67 views

Dominant eigenvalue of sum of tridiagonal and diagonal matrices

Suppose I have a tridiagonal square matrix $A$ of some nice form, for which I know the eigenvalues $\lambda_1<\dots<\lambda_n$. $A$ is also essentially nonnegative (nonnegative everywhere except ...
2
votes
1answer
72 views

An algebraic equation question [closed]

My question is this: If $\frac{\sqrt[n]{\prod_{i=1}^n(p_i + 1)}}{\sqrt[n]{\prod_{i=1}^n(m_i + 1)}} = e ^\beta$ can I find an expression (either exact or approximate) for ...
2
votes
0answers
52 views

Algorithms to find the solutions of a homogenous matrix equations for non-commutative rings

In one paper from 1980 I found a note that there are no known algorithms for solving homogenous matrix equations $x \cdot M = 0$ for matrices which elements belong to a non-commutative ring. (The ...
0
votes
1answer
69 views

Eigendecomposition of a summation of matrices [duplicate]

Can anyone tell me if there's a way to relate the eigendecomposition of the result of a summation of matrices with the eigendecomposition of those matrices? More specifically: If I have a matrix $K = ...
7
votes
1answer
244 views

Casson invariant

Part of the definition of the Casson invariant is that if you have an integer homology sphere $\Sigma$ and a knot $k,$ then $$\lambda(\Sigma + \frac{1}{m} k) - \lambda(\Sigma + \frac{1}{m+1} k)$$ does ...
6
votes
1answer
270 views

Diagonalization for sums of Hermitian matrices

I found an interesting question about diagonalizable matrices, Let $A,B\in \mathcal{M}_n(\mathbb{C})$ Hermitian, such that $AB\neq BA$. Do there exist complex numbers $u\neq v$, such that $A+uB$ and ...
1
vote
0answers
54 views

How do I prove a matrix A is self adjoint to an inner product? . [closed]

In the source question B is an element of $M_n(R)$ and is a symmetic matrix such that $v^tBv>0$. Also $<.|.>$ is an inner product on $R^n$ called the $B$-inner product. we are asked to ...
4
votes
0answers
66 views

Efficiently factorize a KKT system with block diagonal upper corner

I have a system resulting from a quadratic energy minimization with linear equality constraints enforced with Lagrange multipliers which has the form: \begin{equation} A = \left[\begin{array}{c|c} ...
2
votes
1answer
120 views

Symplectic block-diagonalization of a complex symmetric matrix

This is a follow-up question to the one asked here: Given a complex symmetric $2n\times2n$-matrix $A$, i.e., $A\in \mathbb{C}^{2n\times2n}$ with $A = A^T$. Is it possible, to block-diagonalize $A$ ...
1
vote
2answers
48 views

Linear Programm with matrix [closed]

Is there a name for problems like this min norm(Cx) Ax = b where C is a matrix and norm is the maximum norm. This is kind of like a linear Programm. Could this be rewritten as linear programm? Or Any ...
0
votes
1answer
103 views

Collecting terms of a linear expression with nested sums and combinatorics in coefficients

I need to collect the $\Pr(\cdot)$ terms of the following expression: $\sum_{m=3}^{n}\frac{g_{m}\left( \cdot \right) }{\left( \sqrt{\theta \left( 1-\theta \right) }\right) ^{m}}\left[ ...
10
votes
2answers
355 views

Codimension of the range of certain linear operators

Assume that $P(x,y), Q(x,y) \in \mathbb{R}[x,y]$ are two polynomials. We define a linear map $D$ on $\mathbb{R}[x,y]$ with $D(U)=PU_{x}+QU_{y}$. In fact $D$ is the derivational operator correspond ...
4
votes
1answer
110 views

variation of the Lieb concavity theorem

A special case of the well known Lieb concavity theorem states that the following function is concave on positive operators A and B: $$ (A,B) \to \text{Tr} \{A^s X B^{1-s} X^\dagger \} $$ for $s \in ...
1
vote
0answers
42 views

Injectivity of a linear logistic transform

The motivation for this question has to do with neural networks, but it is essentially a purely mathematical question. Suppose you have a perceptron with one hidden layer, a bias, and a logistic ...
6
votes
1answer
215 views

Sets of cardinalities of bases without choice

For a vector space $V$, let $BS(V)$ be the set of cardinalities (not necessarily $\aleph$s) of bases of $V$. Of course, in ZFC each $BS(V)$ is a singleton, but supposing the axiom of choice fails, it ...
0
votes
0answers
73 views

Inverse problem with a rank-1 update

I hope you can help me out with this. I have to find the solution x to an inverse system $$ x=A^{-1}b $$ This inverse problem is basically a least square problem with a rank-1 update. $$ ...
3
votes
0answers
204 views

Find the Range of Function

What is the range of the map $\mathbb{C}^m\to\mathbb{C}^m$, $$(z_1,\ldots,z_m)\mapsto (b_1,\ldots,b_m),$$ where $b_k=\prod_{j\neq k}(z_j-z_k)$ for $1\leq k\leq m$ ?
0
votes
1answer
80 views

Any generic way to move a psd matrix to its neighbors?

Given a two positive matrices $A,B$. For simplicity, let's assume that $Tr A=Tr B=1$. Assume that $\|A-B\|_1\leq\varepsilon$, for some small $\varepsilon>0$, where $\|\cdot\|_1$ is the $l_1$-norm, ...
0
votes
0answers
38 views

Multiplicity of Minimum Eigenvalue of a Convex Combination of Hermitian matrices?

Let $A_1,\dots,A_L$ be $N\times N$ hermitian matrices. Consider the problem \begin{align} \lambda^{\star}=\max_{}&\lambda_{min}\left(\sum_{i=1}^{L}r_iA_i\right) \\ &r_i\geq ...
4
votes
1answer
123 views

Characterization(?) of coersive(?) elements in the special linear group

Take your favorite matrix norm $\|\bullet\|$ (my favorite is the Frobenius norm $\|A\| = \sqrt{\operatorname{tr} A A^t}$). Now consider the set $S_x$ of matrices $A,$ such that $\|A\| < x$ and ...
9
votes
2answers
474 views

What are the invariants of $U\otimes V\otimes W$ under action of $GL(U)\times GL(V) \times GL(W)$

The tensor product of some (finite dimensional real) vector spaces is acted on by the direct product of their general linear groups. I would like to know if there are explicit invariants in the case ...
1
vote
0answers
63 views

Lanczos algorithm with thick restart on a dynamic matrix

currently, I'm working on a way to compute the 2 biggest eigenvalues of a real, symmetric, huge and sparse matrix that changes a few entries from time to time. The problem should be solved using an ...
14
votes
1answer
381 views

Lift chain complex from $\mathbb{F}_2$ to $\mathbb{Z}$

We start with a finite dimensional chain complex over $\mathbb{F}_2$, equipped with a basis. That is, we have finitely many finite dimensional $\mathbb{F}_2$-vector spaces $C_0,\dots,C_k$ with bases ...
1
vote
0answers
45 views

Bounding Rayleigh quotioent for stochastic matrix

Suppose you have an irreducible, stochastic matrix $A$ with left Perron-Frobenius eigenvector $v$ (corresponding to the eigenvalue $1$), and suppose the next largest eigenvalue for $A$ is $\lambda$. ...
3
votes
1answer
153 views

About partial uniqueness of SVD

In order to prove non-uniqueness of singular vectors when a repeated singular value is present, the book (Trefethen-Bau, considered the most authotitative book on the subject), argues as follows: Let ...
3
votes
0answers
42 views

successive schur complements

If I have a large (e.g. 6000x6000), sparse, positive definite matrix $M$ (which may have individual entries everywhere, but most non-zero entries are on / around the diagional). Divide $M$ into blocks ...
5
votes
0answers
250 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 ...
2
votes
0answers
151 views

Norm bound of a complex resolvent

A well known result by Varah states that if $A$ is a strictly diagonally dominant matrix of dimension $n$, then $\|A^{-1}\|_{\infty} \le \max_i\frac{1}{|a_{kk}|-\sum_{j \neq k}|a_{kj}|}$, where the ...
5
votes
1answer
126 views

Simultaneous Tridiagonalization of a given set of hermitian matrices?

I have a set of $N\times N$ hermitian matrices $A_i,~i=1,\dots,M$. Are there any results on the possibility of simultaneously tridiagonalizing them?
5
votes
2answers
319 views

How to check whether a matrix is completely positive or not?

The definition: cone of completely positive matrices $\mathcal{C}=\{\sum_{i=1}^kx_ix_i^T:x_i\in\mathbb{R}^n_+\ for \ i=1,2,...,k\}$. I just don't knwo how to check whether a matrix belongs to ...
3
votes
1answer
98 views

submatrix of a given size with maximum frobenius norm

Let $I\subset \{1,2,\ldots,n\}$, and let $|I|$ denote its cardinality. Now given a Hermitian matrix $\mathbf{A}\in\mathbf{C}^{n\times n}$. I am interested in finding the subset $I$ that maximizes the ...
7
votes
0answers
102 views

When is a product of hyperbolic matrices hyperbolic?

Suppose $A_1,\ldots,A_n$ is a sequence of $2 \times 2$ complex matrices such that $| \det(A_j) | =1$ and $ | \mathrm{tr}(A_j) | > 2 $ for each $j$. What kinds of reasonable restrictions can one ...
1
vote
1answer
146 views

Distributing the Hodge map over the wedge product

Let $(V,\langle,\rangle)$ be a finite dimensional inner product space, $V^{\wedge}$ it exterior algebra, and $\ast$ the Hodge star arising from $\langle,\rangle$. Does there exist any formula to ...
0
votes
0answers
48 views

Compare full-rank probabilities of products of random matrices

Consider two matrices $C_1=A\times B_1$ and $C_2=A\times B_2$, where $A\in\mathbb{F}_q^{N\times K}$, $B_1\in\mathbb{F}_q^{K\times M}$ and $B_2\in\mathbb{F}_2^{K\times M}$; $M\leq N\leq K$. It is ...
0
votes
0answers
77 views

Complexity of turning a d-degree polynomial to 2-degree polynomial

For a very simple example, $(1+x)^4=x^4+4x^3+6x^2+4x+1$ is a 4 degree polynomial, and I want to change it to a 2-degree polynomial by add more variables, for this example, we can simply let $y=x^2$, ...