# Tag Info

## Hot answers tagged linear-algebra

Accepted

### Fastest way to solve a system of linear equations

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$ ...
• 162k

### Inverting a band matrix

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-...
• 532
Accepted

### Why is the probability of a false positive not 0 for Freivald's Algorithm?

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 ...
• 162k

### Suitable choice for moderate-size square matrix multiplication?

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 ...
• 278k
Accepted

### Computing Von Neumann Entropy Efficiently

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 ...
• 5,862
Accepted

### Closed form solution for optimization problem

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. ...
• 3,877

### Proving complexity of computing product of matrices

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 ...
• 162k
Accepted

### Positive Definiteness Constraint

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 ...
• 162k

### How to find subset of vectors whose sum has certain characteristics

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 ...
• 162k

### Fastest way to solve a system of linear equations

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. ...
• 30.7k
Accepted

• 131

### Gauss-Jordan using stacks and list

What you want is called indirection. Instead of physically moving the rows/columns, you move their names. Let's say I call row 1 r[0], and row 3 ...
• 13.6k
Accepted

### Absorbing Markov Chains: An efficient algorithmic approach

There are several possible techniques. Let $P^t$ denote the matrix $P$ raised to the $t$th power. Then $(P^t)_{i,j}$ (the $i,j$-th entry of that matrix) represents the probability that if you start ...
• 162k

### Could a quantum computer perform linear algebra faster than a classical computer?

Here are some pointers: Quantum algorithm for linear systems of equations by Harrow, Hassidim, and Lloyd. This paper shows how to solve sparse systems of linear equations very quickly. Quantum ...
• 278k

### Fastest way to solve a system of linear equations

The best way to solve big linear equations is to use parallelisation or somehow to distribute computations among CPUs or so. See CUDA, OpenCL, OpenMP. A lot of people suggests ...
• 131
Accepted

### Conditions for Linear Diophantine Equations to always have a solution

Short answer: No. Most likely, no useful constraint exists; and it can't be tested in polynomial time. Detailed answer, with justification: It cannot be tested in polynomial time, unless P = NP. In ...
• 162k

### Given matrix $A$, find vector $x$ such that every entry of $Ax$ is nonzero

Define $$M = 1 + \frac{\max_{ij} |A_{ij}|}{\min'_{ij} |A_{ij}|},$$ where the minimum is taken over all non-zero entries. Then the vector $x$ given by $x_j = M^{j-1}$ satisfies your condition. ...
• 278k

### Eigenvalue computation for large graph

There are many methods for computing the eigenvalues of a matrix. If you just want the largest eigenvalue, the power method is an efficient way to do that, as Yuval suggests. Typically the power ...
• 162k

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

You need the eight values to be linearly independent so they form a basis of the space $\{0,1\}^8$.
• 81.9k
Accepted

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

Whether or not Coppersmith-Winograd is the "best" algorithm depends on your circumstances, of course. CW and algorithms like it are usually considered impractical due to high constant factors. ...
• 22.3k
Let us denote the unknowns by $x_1,\ldots,x_n$, and the coefficients by $c_1,\ldots,c_n$. For a polynomial $P(x)$, we denote $$[P(x)] = \sum_{i=1}^n c_i P(x_i).$$ We are given the values of \$[1],[x],...