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_{...


13

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. ...


12

Algorithms can't work over $\mathbb{R}^n$, as you can't represent real numbers in finite space. Also, you can't pick a number uniformly at random from $\mathbb{R}$. Instead, usually we work over a finite field. Then we can't do any better. Suppose we are working in the finite field with two elements, $GF(2)$. Suppose that $$AB - C = \begin{pmatrix} 0 &...


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. ...


9

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-...


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

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 $...


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 ...


8

Since none of the comments gave the concrete answer, I'll write it explicitly here in case anyone needs it (like I did). Firstly, unfortunately, the inverse of a band-limited matrix is a full (non-band-limited) matrix in general, so just filling out the entries of the inverse matrix would take $\Omega\left(n^2\right)$. So I'll assume you just want to solve ...


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

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 ...


7

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 $*$,...


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

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.


6

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 ...


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

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

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

There is what you want to achieve, and there is reality, and sometimes they are in conflict. First you check if your problem is a special case that can be solved quicker, for example a sparse matrix. Then you look for faster algorithms; LU decomposition will end up a bit faster. Then you investigate what Strassen can do for you (which is not very much; it ...


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

The textbook Bellman-Ford algorithm will indeed minimize the span of the variables: $max_i(x_i) - min_i(x_i)$. It involves adding a supernode and 0-weight edges from the supernode to every other nodes in the graph. This is probably what the op is referring to. To maximize $x_n - x_1$, as usual, convert the difference constraints to edges. However, we will ...


4

I have a method for you that will help you find valid solutions (matrices) for many possible values of $m,n$. However, it is not a complete answer to your question. It can try to find a matrix for a particular value of $m,n$, but it might fail, and if it fails, you've learned nothing; my method cannot prove that no such matrix exists. The method is based ...


4

I think you have a misconception. SVM does not necessarily give the latter 58 features a weight of 58/59. Rather, SVM learns what weights to use for each feature, based upon what helps it build the best classifier. So, just use those features and train with them. Don't try to find a way to manually provide different weights for the features; SVM training ...


4

Almost anything involving computer graphics, animation, computer vision, image processing, scientific computing, or simulation of physical phenomena will involve extensive use of vectors and matrices (linear algebra) from simple things like representing spatial transformations and orientations, to very complex algorithms. These things used to be the domain ...


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