# Questions tagged [linear-algebra]

Linear algebra deals with vector spaces and linear transformations.

189 questions
Filter by
Sorted by
Tagged with
141 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 ...
38 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 ...
50 views

58 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 ...
88 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 ...
231 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 ...
323 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-...
65 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 ...
230 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-...
142 views

173 views

### Rank-robustness of the parallel complexity of linear algebra problems

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$, ...
106 views

### Can we make a matrix stable by changing its upper-left submatrix?

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 (...
125 views

### Why are folded Reed Solomon Codes considered non linear?

This is for my understanding. What am I missing?
244 views

### Using an oracle to find a vector $b$ for which $Ax=b$ has a solution

There is an oracle built around a hidden $m\times n$ matrix $A$ all of whose entries are 0 or 1, where $m>n$. The oracle takes as input an integer vector $b$ with positive entries, and answers as ...
115 views

### Non-backtracking paths and the zeta function of graphs

This question has also been posted on mathSE here: https://math.stackexchange.com/questions/2215888/non-backtracking-paths-and-the-ihara-zeta-function For a connected $d$-regular graph $G=(V,E)$ with ...
85 views

83 views

Let $f:\mathbb{F}^n_2\rightarrow \{0,1\}$ be a function constant on an affine subspace $V$ of co-dimension $t$. Assume that that $V$ is a linear subspace, by replacing $f(x)$ with $f(x+v)$ for some $v ... 2answers 616 views ### Estimating the rank of a large sparse matrix Consider a large sparse n by n matrix. Are there any methods to estimate its rank in time roughly proportional the number of elements in the matrix? 2answers 1k views ### Memory requirement for fast matrix multiplication Suppose we want to multiply$n \times n$matrices. The slow matrix multiplication algorithm runs in time$O(n^3)$and uses$O(n^2)$memory. The fastest matrix multiplication runs in time$n^{\omega + ...
Consider a system linear equations in $x$, $Ax =b$, where A is an $n\times n$ matrix, and $b$ is a column vector, and all operations are over $GF(2)$. Is it easier to check satisfiability of the ...