# Questions tagged [linear-algebra]

Linear algebra deals with vector spaces and linear transformations.

206 questions
Filter by
Sorted by
Tagged with
142 views

### complexity class of a function - linear combinations and reductions (Fermionant, immanant, $GL_n$ representations)

The fermionant is a matrix function from physics, which is indexed by a positive integer $k$: \begin{align} \operatorname{Ferm}_k(A) = \sum_{\lambda} d_{\lambda}^{(k)} \operatorname{Imm}_{\lambda^T}(A)...
23 views

### Reference showing global optimality of local minima for matrix factorization

Consider the following matrix factorization problem: Given an $n\times m$ matrix M, find $n\times r$ and $m\times r$ matrices $U$ and $V$ such that $||UV^T - M||_F^2$ is minimized. I have heard it ...
60 views

30 views

### Complexity of best folding of a 2D set (or how to optimize a sandwich)

Motivation: I was making lunch for my son, part of which is making a sandwich from two halves of a slice of bread. In order to minimize the parts of bread that have cheese on them, and are not covered ...
113 views

### Linear regression as a hylomorphism

A hylomorphism consists of an anamorphism followed by a catamorphism. Is it possible to express linear regression as a hylomorphism?
147 views

### Reference for computing the rank of a matrix in polynomial time

In a recent paper, I need to use the fact that computing the rank of a matrix over the integers has polynomial complexity. Given the context, I don't particularly care about the exact asymptotics, as ...
152 views

### Face-splitting product of two Vandermonde matrices: When is is invertible?

Let $A$ and $B$ be two $n^2 \times n$ Vandermonde matrices with coefficients $\alpha_1,\ldots,\alpha_{n^2}$ and $\beta_1,\ldots,\beta_{n^2}$. Let $M$ be the face-splitting product of $A$ and $B$, that ...
82 views

### Complexity of Encoding a Matroid Flow Problem in a Matrix

Context: Take a directed graph $G$ with a specified subset of source vertices $S$ and target vertices $T$. We say a subset $I\subseteq T$ of size $r$ is independent if there exist $r$ distinct ...
210 views

### When is it hard to invert a sparse matrix?

Are cases where numeric inversion of a sparse matrix is known to be harder than sparse matrix multiplication? In practice, sparse matrix inversion is done with methods like Jacobi or Gauss-Seidel, ...
190 views

### What is the complexity of this submatrix selection problem?

We have a $kn\times kn$ matrix $M$ made of $n^2$ many $k\times k$ blocks. We want to find an $n\times n$ submatrix such that each row and column is from distinct window of size $k$ such that the sum ...
52 views

### Computational complexity in linear solvers

I have recently been trying out methods of coding for solving systems of linear equations on Python. Of course, I first used the inbuilt function $\mathit{inv}$ under certain if-conditions to obtain ...
65 views

64 views

### Which invertible linear transformations can be computed reversibly without ancilla/garbage bits just as easily as they can be computed irreversibly?

Suppose that $L:F_{2}^{n}\rightarrow F_{2}^{n}$ is an invertible linear transformation. Then define $w(L)$ to be the gate count of the smallest reversible circuit on $n$ bits without ancilla/garbage ...
91 views

### Why is triangle inequality needed for indexing?

Maybe this is a silly question but I actually can't fulfill that by myself. I'm reading some papers about similarity metrics and I always find that for a distance function $d$ the triangle inequality ...
243 views

### Binary vector $t$ in $span(S)$ over $\mathbb{Z}/q\mathbb{Z}$ for all prime powers $q$ $\Rightarrow$ $t$ in $span(S)$ over $\mathbb{Z}$?

I have a set of $n$ binary vectors $S = \{s_1, \ldots, s_n \} \subseteq \{0,1\}^k \setminus \{1^k\}$ and a target vector $t = 1^k$ which is the all-ones vector. Conjecture: If $t$ can be written as ...
333 views

### Is there a P-complete problem on diophantine equations?

In general deciding whether a diophantine equation has any integer solutions is equivalent to the halting problem. I believe that deciding if a quadratic diophantine equation has any solution is NP-...
66 views

### Minimizing a sum of thresholded quadratics

Let $W_1, \ldots, W_k$ be positive semi-definite matrices, $b_1, \ldots, b_k$ be vectors, and $a_1, \ldots a_k$, $c_1, \ldots, c_k$ be scalars. How difficult is it to find an approximate minimum of ...
240 views

### Algebraic account of Gaussian elimination?

For fun, I've been looking at the interpretation of linear logic in terms of finite-dimensional vector spaces, and ran into an interesting question about the interpretation of double-negation-...
163 views

Suppose we have a $k$-dimensional subspace $V$ in $\mathbb{R}^n$ given by a basis $\{v_1,\cdots,v_k\in \mathbb{R}^n\}$, find an index set $I\subset [n]$ with $|I|=m$ where $k\le m\le n$, such that $$\... 1answer 89 views ### given a set of n points in d-dimensional space and the basis vectors of some subspace, how to find all the points on that space? given a set A of n points with integer coordinates in \mathbb{R}^d, and k<d basis vectors of a subspace K of \mathbb{R}^d, is there an efficient algorithm that returns all points from ... 1answer 89 views ### Some consequences of the Roychowdhury-Orlitsky-Siu result from 1994 This pertains to the proof of theorem 1.1 in this paper, http://dl.acm.org/citation.cfm?id=2897636 So Roychowdhury-Orlitsky-Siu had shown that the number of depth 2 linear threshold gate circuits ... 0answers 62 views ### A random ensemble of sparse boundary operators The following question arises from the study of quantum error correction, and high-dimensional expanders: Is there an algorithm that for given numbers n>0,d≤n,r≤n samples uniformly a linear ... 1answer 93 views ### About the sign-rank of the Minsky-Pappert function Apologies this might be a very trivial thing I am getting confused by! Firstly in corollary 1.1 (page 3) in this paper, https://eccc.weizmann.ac.il/report/2016/075/ the authors claim that they have ... 0answers 84 views ### About Boolean functions with a high sign-rank Recently in this beautiful paper, https://arxiv.org/pdf/1705.02397.pdf it has been shown that there is an explicit Th \circ Th function with sign-rank scaling exponentially in dimension. I wanted to ... 0answers 568 views ### Rank mod 6 vs rank over the reals Let A be a boolean matrix (eg with 0,1 entries). Assume that A has rank \le r both over \mathbb{F}_2 and over \mathbb{F}_3. Does this imply that A has low rank over the reals? This seems ... 1answer 330 views ### "Linear" hashing function Say we have two chunks of data X and Y, which may be of different sizes, is there a non-trivial function hash, and operation *, such that:$$hash(X+Y) = hash(X) * hash(Y) ...where $+$ is ...
It is known that most computational problems related to linear algebra can be computed in $NC^2$ - i.e. for an $n\times n$ matrix $A$, over the reals or a finite field, we can compute the rank of $A$, ...
A matrix $A$ is called strictly stable if its eigenvalues have negative real parts. Given a matrix $A \in \mathbb{R}^{n \times n}$, suppose we can change its upper-left $k \times k$ submatrix at will (...