We’re rewarding the question askers & reputations are being recalculated! Read more.
14

First, this can be solved by linear programming. Let $x_1$, $x_2$, $\ldots$, $x_n$ be your variables. The linear program that solves your question is then $\max t$ subject to $t \leq x_i$, for $i=1 ... n$, $Ax = 0$. If the maximum is 0, then there is no positive solution. If the maximum is $\infty$ (i.e., the linear program is unbounded) then there is a ...


13

Every function on a finite field $GF(q)$ can be represented unique as a polynomial of individual degree at most $q-1$. Indeed, as you mention, $1-x^{q-1} = [\![x=0]\!]$ is a polynomial that equals $1$ if and only if $x=0$. Therefore we can represent any function $f\colon GF(q)^n \to GF(q)$ in the variables $x_1,\ldots,x_n$ in the following form: $$ \sum_{...


11

If you treat your vectors as over the field $GF(2)$ rather than over the set $\{0,1\}$, then what you ask is to find a basis for the span of a set of vectors. This is a well-studied problem in linear algebra, which you probably know the solution for. (One option is Gaussian elimination.)


10

The parts that you mentioned are basic concepts of linear algebra. You cannot understand the more advanced concepts (say, eigenvalues and eigenvectors) before first understanding the basic concepts. There are no shortcuts in mathematics. Without an intuitive understanding of the concepts of span and linear independence you won't get far in linear algebra. ...


10

A LU decomposition of a $n \times n$ matrix can be computed in $O(M(n))$ time, where $M(n)$ is the time to multiply two $n \times n$ matrices. Therefore, you can find a solution to a system of $n$ linear equations in $n$ unknowns in $O(M(n))$ time. For instance, Strassen's algorithm achieves $M(n) = O(n^{2.8})$, which is faster than Gaussian elimination. ...


9

Your problem is NP-complete, by reduction from Subset Sum (it is in NP since the fact that everything is non-negative bounds the coefficients of the solution sufficiently well). Given an instance $S = \{s_1,\ldots,s_n\}, T$ of Subset Sum (is there a subset of $S$ summing to $T$?), we construct an instance $v_1,\ldots,v_{2n},u$ of your problem as follows. For ...


8

Graph isomorphism has been mentioned along with primality testing as early as 1971 in Cook's famous paper on NP-completeness. Cook mentions that he was unable to prove the NP-completeness of both problems. Nowadays we known that primality testing is in P, but the status of graph isomorphism is still unknown. Most experts conjecture that it is "NP-...


8

This is related to an open research question, which is known as the "Online Boolean Matrix-Vector Multiplication (OMv) problem". This problem reads as follows (see [1]): Given a binary $n \times n$ matrix $M$ and $n$ binary column vectors $v_1, \dots, v_n$, we need to compute $M v_i$ before $v_{i+1}$ arrives. Notice that the problem from the question is ...


7

First of all, people tend to forget that $\omega$ is an infimum. Whenever we write $O(n^\omega)$, we actually mean for all $\gamma > \omega$, there is an algorithm running in time $O_\gamma(n^\gamma)$. Keller-Gehrig showed (among else) how to present a matrix $A$ in rank normal form in time $O(n^\omega)$. If $A$ has rank $r$, then a rank normal form of $...


7

You misread the text. The authors of PETSc are just telling you that you can't avoid Amdahl's law. They have done their best to parallelize every aspect of the linear solver. But a real program is not just a call to a linear solver. First you generate a matrix and then you pass the matrix to the linear solver. If your matrix generator is slow, your ...


7

Linear algebra is sometimes extremely useful and powerful in graph algorithms. With the matrix-tree theorem you can efficiently count the number of spanning trees a graph has (you need to understand eigenvalues). A more challenging application, where you need an even firmer grasp of linear algebra is the FKT algorithm for computing the number of perfect ...


7

Dumas and Pan recently wrote a non-asymptotic survey of fast matrix multiplication in practice, which hopefully answers your questions. They concentrate on matrices of order at most a million, and list all relevant algorithms.


6

Restating the problem. As far as I can tell, your system is equivalent to the following: $$c_1 x_1 + \dots + c_n x_n = N$$ subject to the constraints $$0 \le x_1, \dots, x_n \le 1.$$ Solving this problem. This is a linear program, so certainly we can tell in polynomial time whether it has any feasible solution, as a result of the fact that there are ...


6

You can also "transpose" a matrix in $O(1)$ time and space. Maintain a bit $t$ for your matrix $M$. Whenever $M$ is transposed, flip $t$. Now, consider accessing an entry in $M$. If $t$ is set to true, return $M[j,i]$ instead of $M[i,j]$. This trick is arguably cheating, but not always is the matrix actually needed to be transposed. This might work nicely ...


6

The sequence you (correctly) identified sums up to $\frac{n(n-1)}{2}=\theta(n^2)$, which gives the runtime you were looking for. I'm not sure what you are referring to by "leading constants". Do you mean you can ignore e.g. $1+2+3$ ? sure, but that will reduce $6$ from the complexity, which is clearly meaningless. On the other hand, you cannot ignore $f(n)$ ...


6

Multiplying by the $n * p$ matrix decreases the dimensionality of the data set. Think of this as projecting the highly dimensional space into a smaller dimensional space. For example, you could do principle component analysis and project it into a small space. This way things that are correlated together are projected into the same dimension and if one of ...


6

There is (unless $P=NP$) no polynomial time algorithm for this problem, since the problem is $NP$-hard by reduction from Subset Sum. If you set $l_i=u_i$ then the problem is to determine if there is a subset of the $u_i$ that sums to $C$ (which is the Subset Sum problem). If your problem did not allow $l_i=u_i$, if you were to require that $l_i<x_i<...


5

Valiant proved that the permanent is $\# P$-complete, which means that an efficient algorithm for computing the permanent can be used to solve any problem in $\# P$, such as counting the number of satisfying assignment to a CNF, the number of Hamiltonian circuits, the number of $k$-colorings and so on. In particular, it could be used to solve NP-complete ...


5

One of the most well known uses of linear algebra is in Google's Pagerank algorithm: The PageRank values are the entries of the dominant left eigenvector of the modified adjacency matrix.


5

The algebraic proof goes like this. Fix a number of vertices $n$, and consider the "formal Laplacian" $n \times n$ matrix defined by $$ \begin{align*} L(i,i) &= \sum_{j \neq i} X(i,j) \\ L(i,j) &= - X(i,j). \end{align*} $$ Here the $X(i,j)$ are commuting indeterminates. For every spanning tree $T$ of the complete graph $K_n$ we can associate a degree ...


5

If it is possible try to exploit banded tridiagonal nature of matrix. Otherwise if the matrix contains only a constant number of distinct values (which surely is being binary), you should try Mailman algorithm (by Edo Liberty, Steven W. Zucker In Yale university technical report #1402): optimized over finite dictionary Common Subexpression Elimination is ...


5

I don't think there's any general algorithm that works for arbitrary semirings. The requirement to be a semiring doesn't give us a lot to work with. However, if you have a closed semiring, then there are algorithms for solving systems of linear equations over the semiring. Closed semirings A closed semiring is a semiring with a closure operator, denoted $...


5

A paper Computing the Entropy of a Large Matrix by Thomas P. Wihler, Bänz Bessire, André Stefanov suggests approximating $x \lg x$ with a polynomial. Then you can use the trace of powers of the matrix to sum the results of applying that polynomial to each of the eigenvalues. (The polynomial-via-power-and-trace thing works because density matrices have ...


5

I'm afraid you can't. As I mentioned in my response to your previous question: The complexity of a problem is the running time of the fastest algorithm for that problem. There exist algorithms for this problem whose running time is much less than $N^3$. As I described in my previous answer, there are much more efficient algorithms for matrix inversion (...


5

There is a closed-form solution to your problem, but first it helps to know two facts to derive the minimizer. The first fact is that we can re-write the Frobenius norm squared as a trace operation. Namely, $$\|C\|^2_F = \text{Tr}\left[CC'\right],$$ where $C'$ denotes the transpose of $C$. The second fact is the derivative of the Frobenius norm squared, ...


5

A matrix $A$ is positive semidefinite if and only if there exists a matrix $V$ such that $$A = V^\top V.$$ So, you can use the entries of $V$ as your unknowns, and express each entry of $A$ as a quadratic function of the unknowns. Whenever you want to use $A$, instead rewrite that equation in terms of the entries of $V$.


5

The question has changed. I'll answer the updated question. Here are three candidate algorithms; the first is faster than $O(m^n)$ time, and the second might be faster as well for some parameter values. I will assume that the vectors are from $\mathbb{R}^d$, i.e., $d$-dimensional vectors (in your example $d=3$). Try all subsets There are exactly ${n \...


5

You have recalled the correct category, "linear-algebra". Let us see how we can interpret xor in the terms of linear-algebra. Here is the computation rules for xor. $$0\oplus0=0$$ $$0\oplus1=1$$ $$1\oplus0=1$$ $$1\oplus1=0$$ If we consider 0 and 1 as the zero element and the unit element of the binary field $\Bbb F_2$, the simplest finite field, then we can ...


4

This is a bipartite matching problem, which has several known algorithms. As a bonus, you get a combinatorial criterion for when it is even possible (namely, Hall's theorem). Construct a bipartite graph with $n$ vertices on each side $x_i,y_j$. Connect $x_i$ to $y_j$ if $A_{ij} \neq 0$. A maximum matching in this graph, if it involves all the vertices, ...


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