# Questions tagged [linear-algebra]

The tag has no usage guidance.

191 questions
Filter by
Sorted by
Tagged with
13 views

### N-dimensional generalization of map and reduce?

Is there any conceptual generalization of higher-order functions like map and reduce but for N-dimensional objects (e.g. arrays or tensors)? For mapping, I guess it would be a point-wise ...
26 views

### Seeking guidance on what to read for Feasibility Binary IP with ''almost total unimodular'' (-1, 0, 1)-Coefficient Matrix and No Obj Function

I am working on an algorithm in graph theory which I wish to prove it's polynomiality/NP-hardness. I am investigating a binary variable (0, 1) integer program which has the coefficient matrix ...
57 views

### How does the sweep line algorithm check for intersection using vector cross product?

I am trying my best to understand the sweep-line algorithm to find line intersections. I have understood most of the intuition except how it is calculating the intersection between 2 line segments ...
46 views

### When does Gaussian elimination solve exact 1-in-3 SAT?

Terms: A literal is a variable or its negation. A clause is a set of literals. An exact 3-in-1 clause is satisfied if an assignment of values to variables results in exactly 1 ...
39 views

38 views

### Geometric median of two disjoint sets of points lies on line between their respective medians

I was working on a problem about geometric medians and I had an idea for a divide and conquer solution, but it would only work if a set of points, when split into two disjoint sets, and those sets ...
54 views

### How to quickly solve a linear equation for 7000 times?

I need to solve a linear equation Ax=b for 7000 times (A is sparse and complex square matrix), and at each time only 4 elements (A(i,k), A(i,m), A(j,k) and A(j,m)) are changed while all other elements ...
36 views

### How to make sure matrix completion can generate a matrix with values in expected range?

I am doing a matrix completion project. Assume that I have an incomplete matrix like ...
37 views

95 views

### What is the fastest algorithm to establish whether a linear system in $\mathbb{R}$ has a solution?

I know the best algorithm to solve a linear system in $\mathbb{R}$ with $n$ variables is Coppersmith-Winograd's algorithm, which has a complexity of $$O\left(n^{2.376}\right).$$ How much easier is ...
243 views

### Transforming a byte with a subset of a small, fixed set of values and xor into any other value

If I have some collection of bits, -- a byte, say -- of arbitrary value then I can transform it into some other value by means of exclusive-oring it with a subset of (in this case) eight fixed values, ...
34 views

### Smallest Circuit for Square of Sparse Symmetric Matrix

I have an n by n symmetric matrix, and I would like to compute its square in as small a circuit complexity as possible. It's sparse: there are sqrt(n) nonzero entries in each row/column, so the input ...
38 views

### Sublinear Homomorphism Property Testing Counter Example

This is a homework question, so I'm not looking for answers, just general guidance. I'm looking at a Sublinear Algorithms survey where (Group) Homomorphism property testing is discussed. The case of ...
49 views

42 views

### Check if no linear combination is within a hypercube

Shapes Let $C$ be the unit hypercube in $\mathbb{R}^{n}$. Let $\vec{o}$ be a point in $\mathbb{R}^{n}$. Let $B$ be a $n \times m$ matrix. The columns of $B$ are a set of linearly independent vectors ...
Given rank deficient matrix $A$, I want to randomly construct vectors $\vec{x}$ such that: $0 \le x_{j} \le 1$ $0 \le b_{j} \le 1$ where $\vec{b} = A\vec{x}$ Matrix $A$ is about 10 x 15. I want to ...
### Sparse feasible solution $|x|_0\le k$ for system of linear inequalities $A x \le b$
Suppose the set of linear inequalities $Ax\le b$, in which $A\in\mathbb{R}^{m\times n},x,b\in\mathbb{R}^n$ is given. Is it possible to determine in polynomial time with regard to $m$ and $n$ if there ...