# Tag Info

### Alternatives to SVD for rank factorization

The proper search term in scientific journals is "Rank-Revealing Decomposition". If You want some theoretic guarantees on numeric accuracy/stability, the search term would be "Strong ...
• 991

### How does numpy.linalg.inv calculate the inverse of a matrix?

The source code of this function is here, which is a wrapper for a C++ function here, which is calling some BLAS/LAPACK library functions. Specifically, in order to compute the inverse of a matrix $A$,...
• 8,248

### Can any SAT problem be converted to a system of linear equations over $\mathbf{Z}_2$?

Equivalence: Not every SAT instance can be expressed as a system of linear equations. For instance, $x_1 \lor x_2$ cannot be expressed as a system of linear equations. (Why not? Systems of linear ...
• 159k
Accepted

### Can a linear programming method be used to solve systems of inequalities with OR (disparate) compound inequalities?

First off, a couple of observations. If you allow three inequalities in each "compound inequality", then the problem of finding a feasible solution is NP-complete, since any 3-SAT problem ...
• 22.1k

### Finding a vector of maximum Hamming distance from a subspace of $(\mathbb{Z}/2\mathbb{Z})^n$

Your problem is very likely NP-hard. If you don't add the restriction that $W$ is sub-space, but just receive a set of boolean vectors $W$, then it is NP-hard and known as a Covering Radius proven NP-...
1 vote

### Given a set of points $S$ which is a subset of a vector space $V$, find the smallest subspace which intersect $S$ in at least $k$ points

In general, this problem is hard. For instance, if we have a vector space over $GF(2)$, then checking whether there is a one-dimensional subspace $A$ with the desired property is as hard as learning ...
• 159k
1 vote
Accepted

The notation $$(x_i)_{i \in \{1,\dots,n\}}$$ is short-hand for $$(x_1,x_2,\dots,x_n).$$ Just two different ways to write the same thing. It is analogous to the relationship between $\sum_{i \in \{1,\... • 159k 1 vote ### Mathematical operation for removing duplicate rows in a matrix A more efficient approach is to hash each row, insert them into a hash table, and find duplicates in that way. The running time will be$O(n^2)$. You can implement something like this using only ... • 159k 1 vote Accepted ### Finding solution to Mv=v over$\mathbb{Z}$={0,1} for matrix M given a set linearly independent v It is not possible. Such matrices don't exist. We always have$Mv=v$whenever$v=0$(the all-zeros vector). No set that contains the all-zeros vector is linearly independent, so surely$0 \notin V$.... • 159k 1 vote ### Efficient algorithm for finding a vector to maximize the number of positive dot products with a given set (finding the maximum overlap of half-spaces) If I understand your question correctly, you are describing a problem that is almost identical to the optimization problem in Support Vector Machines. The only difference is that in your case the ... • 991 1 vote ### Solving systems of linear equations over semirings Even for the canonical example of a semiring,$\mathbb N\$, solving linear equations is hard; in a sense, NP-hard. See 0-1 Knapsack Problem, and Integer Knapsack Problem (Papadimitriou and Steiglitz, ...

Only top scored, non community-wiki answers of a minimum length are eligible