# Questions tagged [linear-algebra]

Linear algebra deals with vector spaces and linear transformations.

185 questions
Filter by
Sorted by
Tagged with
132 views

### What are some good resources for strengthening my theoretical foundation for machine learning?

I'm a computer science major and I'm taking a lot of machine learning courses. I'm finding that my theoretical foundation on subjects like calculus and linear algebra are not as strong as I'd like ...
5k views

### Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time

It is commonly believed that for all $\epsilon > 0$, it is possible to multiply two $n \times n$ matrices in $O(n^{2 + \epsilon})$ time. Some discussion is here. I have asked some people who are ...
137 views

807 views

### Is there a polynomial time algorithm to determine if the span of a set of matrices contains a permutation matrix?

I would like to find a polynomial time algorithm that determines if the span of a given set of matrices contains a permutation matrix. If any one knows if this problem is of a different complexity ...
569 views

### Matrix multiplication algorithms for research

I am implementing a matrix library for use in my research. This should support 2D matrices of size 100x100 (or more perhaps later on). I am a little confused about the algorithm I should be using for ...
141 views

### Complexity of eigenvalue problem

Many matrix diagonalization algorithms have time complexity $\mathcal{O}(n^3)$ where $n$ is the number of columns/raws (consider only square matrices). What is the best time lower bound it is known? ...
256 views

3k views

### Evidence that matrix multiplication can be done in quadratic time?

It is widely conjectured that $\omega$, the optimal exponent for matrix multiplication, is in fact equal to 2. My question is simple: What reasons do we have for believing that $\omega = 2$? I'm ...
476 views

### The minimum number of arithmetic operations to compute the determinant

Has there been any work on finding the minimum number of elementary arithmetic operations needed to compute the determinant of an $n$ by $n$ matrix for small and fixed $n$? For example, $n=5$.
### Given a matrix $A$ maximize the number of positive elements in $Ax$ under specific constraints for $x$
Let $A = [a_{ij}]$ be a symmetric matrix with nonnegative values and $k << n/2$ a given constant. We want to rearrange the columns of the matrix such that the number of rows with the following ...